Search

Abstract: For a vertex of a graph , let be the set of with all of its neighbors in . A set of vertices is an identifying code of if the sets are nonempty and distinct for all vertices . If admits an identifying code, we say that is identifiable and denote by the minimum cardinality of an identifying code of . In this paper, we study the identifying code of the corona product of graphs and . We first give a necessary and sufficient condition for the corona product to be identifiable, and then express in terms of and the (total) domination number of . Finally, we compute for some special graphs . [Copyright &y& Elsevier]

Letbe the 2ν-dimensional symplectic space over a finite field 𝔽q, and let ℳ be a given nontrivial orbit of subspaces inunder the symplectic groupSp2ν(𝔽q). Denote by 𝒫 the set of subspaces which are intersections of subspaces in ℳ. By ordering 𝒫 by inclusion, 𝒫 is a finite graded poset. In this article we show that 𝒫 has the normalized matching (NM) property, which implies that 𝒫 has the strong Sperner property and the Lubell-Yamamoto-Meschalkin (LYM) property. [ABSTRACT FROM PUBLISHER]

Abstract: In Suzuki (1998) [7] Suzuki gave a classification of association schemes with multiple Q-polynomial structures, allowing for one exceptional case which has five classes. In this paper, we rule out the existence of this case. Hence Suzukiʼs theorem mirrors exactly the well-known counterpart for association schemes with multiple P-polynomial structures, a result due to Eiichi Bannai and Etsuko Bannai in 1980. [Copyright &y& Elsevier]

Abstract: Meemark and Prinyasart [10] proved by combinatorial method that the symplectic graph modulo is strongly regular when , and is arc transitive when p is an odd prime. In this paper, combining matrix method and elementary number theory, we continue this research, and prove that is arc transitive for any prime p. Furthermore, we determine the suborbits of the symplectic group modulo on , and show that is a strictly Deza graph when and . [Copyright &y& Elsevier]

A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. An infinite family of cubic 1-regular graphs was constructed in European J. Combin. 23 (2002) 559, as cyclic coverings of the three-dimensional hypercube Q3. In this paper, we classify the s-regular cyclic coverings of Q3 for each s≥1, whose fibre-preserving automorphism subgroups act arc-transitively. As a result, a new infinite family of cubic 1-regular graphs is constructed. [Copyright &y& Elsevier]

FORMIN proteins, which contain FH1 and FH2 domains, play crucial roles in the growth and development of organisms. However, the functions of FORMINs in rice (Oryza sativa) remain largely unclear. In this study, a total of 17 FORMIN genes in rice genome were identified, and their distribution on chromosomes, gene structure, as well as protein structure were investigated. According to their protein structural and phylogenetic features, these 17 rice FORMIN genes were classified into two distinct subfamilies. The results of subcellular localization prediction showed that rice FORMINs were located in cytosol, Golgi complex, endoplasmic reticulum, extracellular, or vacuole. Protein–protein interaction (PPI) prediction results showed that FORMIN proteins might answer hormone signals and be involved in cytoskeleton dynamics regulation and cell wall morphology regulation. The gene expression analysis by using qRT-PCR indicated that a number of rice FORMIN genes were induced by auxin/indole-3-acetic acid (Aux/IAA) and abscisic acid (ABA). Importantly, some of the FORMIN genes also exhibited cadmium (Cd) and drought stress-responding expression patterns, suggesting that FORMIN genes may play roles in rice while dealing with drought or Cd stress. Overall, our research may shed light on the understanding of the biological functions of rice FORMINs. [ABSTRACT FROM AUTHOR]

Abstract Let Z p s be the residue class ring of integers modulo p s , where p is a prime number and s is a positive integer. We study subspaces and Grassmann graphs for Z p s n. A Grassmann graph for Z p s n , denoted by G d (n , m , p s) (G d for short), has all m -subspaces of Z p s n as its vertices, and two distinct vertices are adjacent if their intersection is of dimension > m − d , where m < n and 2 ≤ d ≤ m + 1. We give the clique number and geometric structures of maximum cliques of G d , etc. By these results, we obtain the Erdős–Ko–Rado theorem for Z p s n and some bounds of the independence number of G d. We also show that an optimal Grassmannian code for Z p s n is a largest independent set of G d. A p s -Kneser graph over Z p s , denoted by Z p s K n : m where n ≥ 2 m ≥ 4 , is the complement of G m (n , m , p s). Finally, we prove that Z p s K n : m is a core when n > 2 m ≥ 4 , and give some estimations for the chromatic number and clique number of Z p s K n : m. [ABSTRACT FROM AUTHOR]

In this paper, we classify commutative weakly distance-regular digraphs of valency 3 with girth more than 2 and one type of arcs. Combining [8, Theorem 1.2] , [10, Theorem 1.3] and [11, Theorem 1] , commutative weakly distance-regular digraphs of valency 3 are completely determined. [ABSTRACT FROM AUTHOR]

We characterize the strong metric dimension of the power graph of a finite group. As applications, we compute the strong metric dimension of the power graph of a cyclic group, an abelian group, a dihedral group and a generalized quaternion group. [ABSTRACT FROM AUTHOR]

The power index $$\Theta (\Gamma )$$ of a graph $$\Gamma $$ is the least order of a group G such that $$\Gamma $$ can embed into the power graph of G. Furthermore, this group G is $$\Gamma $$ -optimal if G has order $$\Theta (\Gamma )$$ . We say that $$\Gamma $$ is power-critical if its order is equal to $$\Theta (\Gamma )$$ . This paper focuses on the power indices of complete graphs, complete bipartite graphs and 1-factors. We classify all power-critical graphs $$\Gamma '$$ in these three families, and give a necessary and sufficient condition for $$\Gamma '$$ -optimal groups. [ABSTRACT FROM AUTHOR]

Let V be an ( n + l ) -dimensional vector space over the finite field F q with l ≥ n > 0 , and W be a fixed l -dimensional subspace of V . Suppose F is a non-trivial intersecting family of n -dimensional subspaces U of V with U ∩ W = 0 . In this paper, we give the tight upper bound for the size of F , and describe the structure of F which reaches the upper bound. [ABSTRACT FROM AUTHOR]

A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. An interesting problem in graph theory is to distinguish whether a graph is a core. The twisted Grassmann graphs, constructed by van Dam and Koolen in (Invent Math 162:189-193, 2005), are the first known family of non-vertex-transitive distance-regular graphs with unbounded diameter. In this paper, we show that every twisted Grassmann graph is a pseudo-core. [ABSTRACT FROM AUTHOR]

This paper studies the rainbow connection number of the power graph $$\Gamma _G$$ of a finite group G. We determine the rainbow connection number of $$\Gamma _G$$ if G has maximal involutions or is nilpotent, and show that the rainbow connection number of $$\Gamma _G$$ is at most three if G has no maximal involutions. The rainbow connection numbers of power graphs of some nonnilpotent groups are also given. [ABSTRACT FROM AUTHOR]

We describe the full automorphism group of the power (di)graph of a finite group. As an application, we solve a conjecture proposed by Doostabadi, Erfanian and Jafarzadeh in 2013. [ABSTRACT FROM AUTHOR]

In this paper, by shifting technique we study t -intersecting families for direct products where the ground set is divided into several parts. Assuming the size of each part is sufficiently large, we determine all extremal t -intersecting families for direct products. We also prove that every largest t -intersecting subfamily of a more general family introduced by Katona is trivial under certain conditions. [ABSTRACT FROM AUTHOR]

The power graph P G of a finite group G is the graph with the vertex set G , where two distinct vertices are adjacent if one is a power of the other. We first show that P G has a transitive orientation, so it is a perfect graph and its core is a complete graph. Then we use the poset on all cyclic subgroups of G (under usual inclusion) to characterize the structure of P G . Finally, a closed formula for the metric dimension of P G is established. As an application, we compute the metric dimension of the power graph of a cyclic group. [ABSTRACT FROM AUTHOR]

Abstract: Assume that is a positive integer and or 2. In this paper we introduce the orthogonal graph over a Galois ring of odd characteristic and prove that it is arc transitive. Moreover, we compute its parameters as a quasi-strongly regular graph. In particular, we show that is a strongly regular graph and is a strictly Deza graph when . [Copyright &y& Elsevier]

Abstract: In Arumugam et al. (2013), Arumugam et al. studied the fractional metric dimension of the Cartesian product of two graphs, and proposed four open problems. In this paper, we determine the fractional metric dimension of vertex-transitive graphs, in particular, the fractional metric dimension of a vertex-transitive, distance-regular graph is expressed in terms of its intersection numbers. As an application, we calculate the fractional metric dimension of Hamming graphs and Johnson graphs, respectively. Moreover, we give an inequality for metric dimension and fractional metric dimension of an arbitrary graph, and determine all graphs for which the equality holds. Finally, we establish bounds on the fractional metric dimension of the Cartesian product of graphs. As a result, we completely solve the four open problems. [Copyright &y& Elsevier]

Abstract: Huang (1987) [8] proved the Erdős–Ko–Rado theorem for attenuated spaces. In this paper, we generalize Huangʼs result for singular linear spaces. [Copyright &y& Elsevier]

Let n , r , k 1 , ... , k r and t be positive integers with r ≥ 2 , and F i (1 ≤ i ≤ r) a family of k i -subsets of an n -set V. The families F 1 , F 2 , ... , F r are said to be r -cross t -intersecting if | F 1 ∩ F 2 ∩ ⋯ ∩ F r | ≥ t for all F i ∈ F i (1 ≤ i ≤ r) , and said to be non-trivial if | ∩ 1 ≤ i ≤ r ∩ F ∈ F i F | < t. If the r -cross t -intersecting families F 1 , ... , F r satisfy F 1 = ⋯ = F r = F , then F is well known as r -wise t -intersecting. In this paper, we first describe the structure of maximal 2-cross t -intersecting families with given t -covering numbers and then determine the structure of non-trivial 2-cross t -intersecting families with maximum product of their sizes. We also give a stability result for the non-trivial r -wise t -intersecting families with maximum size for r ≥ 3. [ABSTRACT FROM AUTHOR]

Abstract: Let be the -dimensional symplectic space over the finite field . In this paper, we compute the size of a family of special subspaces in , and discuss its applications to the constructions of Cartesian authentication codes, pooling designs and strongly regularized semilattices, respectively. [Copyright &y& Elsevier]

Abstract: Let be a (di)graph. A set of vertices in is a resolving set of if every vertex of is uniquely determined by its vector of distances to all the vertices in . The metric dimension of is the minimum cardinality of all the resolving sets of . In this paper we study the metric dimension of the line graph of . In particular, we show that for a strongly connected digraph which is not a directed cycle, where is the vertex set and is the edge set of . As a corollary, the metric dimension of de Bruijn digraphs and Kautz digraphs is given. Moreover, we prove that for a simple connected graph with at least five vertices, where is the maximum degree of . Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters. [Copyright &y& Elsevier]

In this paper, we describe the structure of maximal non-trivial uniform t -intersecting families with large size for finite sets. In the special case when t = 1 , our result gives rise to Kostochka and Mubayi's result in 2017. [ABSTRACT FROM AUTHOR]

• We obtain the upper bounds for the number of edges in even-cycle-free subgraphs of the complete transposition graphs, which are a family of bipartite and arctransitive graphs. • A family of new auxiliary graphs related to the complete transposition graphs are constructed and used in order to obtain the upper bounds. • A new Ramsey-type result for the complete transposition graphs is obtained. Given graphs G and H , the generalized Turán number ex (G , H) is the maximum number of edges in an H -free subgraph of G. In this paper, we obtain an asymptotic upper bound on ex (C T n , C 2 ℓ) for any n ≥ 3 and ℓ ≥ 2 , where C 2 ℓ is the cycle of length 2 ℓ and C T n is the complete transposition graph which is defined as the Cayley graph on the symmetric group S n with respect to the set of all transpositions of S n. [ABSTRACT FROM AUTHOR]

• We obtain the upper bounds for the number of edges in even cycle free subgraphs of the doubled Johnson graphs, which are well studied subgraphs of the famous hypercube graphs. • A family of new auxiliary graphs related to doubled Johnson graphs are constructed and used in order to obtain the upper bounds. • A new Ramsey type result for doubled Odd graphs is obtained. The generalized Turán number ex (G , H) is the maximum number of edges in an H -free subgraph of a graph G. It is an important extension of the classical Turán number ex (n , H) , which is the maximum number of edges in a graph with n vertices that does not contain H as a subgraph. In this paper, we consider the maximum number of edges in an even-cycle-free subgraph of the doubled Johnson graphs J (n ; k , k + 1) , which are bipartite subgraphs of hypercube graphs. We give an upper bound for ex (J (n ; k , k + 1) , C 2 r) with any fixed k ∈ Z + and any n ∈ Z + with n ≥ 2 k + 1. We also give an upper bound for ex (J (2 k + 1 ; k , k + 1) , C 2 r) with any k ∈ Z + , where J (2 k + 1 ; k , k + 1) is known as doubled Odd graph O ˜ k + 1. This bound induces that the number of edges in any C 2 r -free subgraph of O ˜ k + 1 is o (e ( O ˜ k + 1)) for r ≥ 6 , which also implies a Ramsey-type result. [ABSTRACT FROM AUTHOR]

Let V be an n -dimensional vector space over the finite field F q , and [ V k ] denote the family of all k -dimensional subspaces of V. The families F 1 ⊆ [ V k 1 ] , F 2 ⊆ [ V k 2 ] , ... , F r ⊆ [ V k r ] are said to be r -cross t -intersecting if dim ⁡ (F 1 ∩ F 2 ∩ ⋯ ∩ F r) ≥ t for all F i ∈ F i , 1 ≤ i ≤ r. The r -cross t -intersecting families F 1 , F 2 , ... , F r are said to be non-trivial if dim ⁡ (∩ 1 ≤ i ≤ r ∩ F ∈ F i F) < t. In this paper, we first determine the structure of r -cross t -intersecting families with maximum product of their sizes. As a consequence, we partially prove one of Frankl and Tokushige's conjectures about r -cross 1-intersecting families for vector spaces. Then we describe the structure of non-trivial r -cross t -intersecting families F 1 , F 2 , ... , F r with maximum product of their sizes under the assumptions r = 2 and F 1 = F 2 = ⋯ = F r = F , respectively, where the F in the latter assumption is well known as r -wise t -intersecting family. Meanwhile, stability results for non-trivial r -wise t -intersecting families are also been proved. [ABSTRACT FROM AUTHOR]