Search

Let $\mathcal{F}$ be a family of $k$-subsets of an $n$-set. Write $\mathcal{D}_{\mathcal{F}}(H;t)=\left\{ F\in\mathcal{F}: \left|F\cap H\right|

Bollob\'as-type theorem determines the maximum cardinality of a Bollob\'as system of sets. The original result has been extended to various mathematical structures beyond sets, including vector spaces and affine spaces. This paper generalizes the Bollob\'as-type theorem to singular linear spaces, and determine the maximum cardinality of (skew) Bollob\'as systems on them.

Weakly distance-regular digraphs are a natural directed version of distance-regular graphs. In [16], we classified all commutative weakly distance-regular digraphs whose underlying graphs are Hamming graphs, folded n-cubes, or Doob graphs. In this paper, we classify all commutative weakly distance-regular digraphs whose underlying graphs are Johnson graphs or folded Johnson graphs.

Let $V$ be a finite dimensional vector space over a finite field, and $\mathcal{F}$ a family consisting of $k$-subspaces of $V$. The family $\mathcal{F}$ is called $t$-intersecting if $\dim(F_{1}\cap F_{2})\geq t$ for any $F_{1}, F_{2}\in \mathcal{F}$. We say $\mathcal{F}$ is almost $t$-intersecting if for each $F\in \mathcal{F}$ there is at most one member $F^{\prime}$ of $\mathcal{F}$ such that $\dim(F\cap F^{\prime})

A digraph is semicomplete if any two vertices are connected by at least one arc and is locally semicomplete if the out-neighbourhood (resp. in-neighbourhood) of any vertex induces a semicomplete digraph. In this paper, we characterize all locally semicomplete weakly distance-regular digraphs under the assumption of commutativity.

Let $V$ be a finite dimensional vector space over a finite field. Suppose that $\mathscr{F}_1$, $\mathscr{F}_2$, $\dots$, $\mathscr{F}_r$ are $r$-cross $t$-intersecting families of $k$-subspaces of $V$. In this paper, we determine the extremal structure when $\prod_{i=1}^r|\mathscr{F}_i|$ is maximum under the condition that $\dim(\bigcap_{F\in\mathscr{F}_i}F)

We classify certain non-symmetric commutative association schemes. As an application, we determine all the weakly distance-regular circulants of one type of arcs by using Schur rings. We also give the classification of primitive weakly distance-regular circulants., Comment: 28 pages

Weakly distance-regular digraphs are a natural directed version of distance-regular graphs. In [8], the third author and Suzuki proposed a question when an orientation of a distance-regular graph defines a weakly distance-regular digraph. In this paper, we initiate this project, and classify all commutative weakly distance-regular digraphs whose underlying graphs are Hamming graphs, folded n-cubes and Doob graphs, respectively.

A weakly distance-regular digraph is $P$-polynomial if its attached scheme is $P$-polynomial. In this paper, we characterize all $P$-polynomial weakly distance-regular digraphs.

Let $n$, $r$, $k_1,\ldots,k_r$ and $t$ be positive integers with $r\geq 2$, and $\mathcal{F}_i\ (1\leq i\leq r)$ a family of $k_i$-subsets of an $n$-set $V$. The families $\mathcal{F}_1,\ \mathcal{F}_2,\ldots,\mathcal{F}_r$ are said to be $r$-cross $t$-intersecting if $|F_1\cap F_2\cap\cdots\cap F_r|\geq t$ for all $F_i\in\mathcal{F}_i\ (1\leq i\leq r),$ and said to be non-trivial if $|\cap_{1\leq i\leq r}\cap_{F\in\mathcal{F}_i}F|

Let $\mathscr{P}$ be a symplectic polar space over a finite field $\mathbb{F}_q$, and $\mathscr{P}_m$ denote the collection of all $k$-dimensional totally isotropic subspace in $\mathscr{P}$. Let $\mathscr{F}_1\subset\mathscr{P}_{m_1}$ and $\mathscr{F}_2\subset\mathscr{P}_{m_2}$ satisfy $\dim(F_1\cap F_2)\ge t$ for any $F_1\in\mathscr{F}_1$ and $F_2\in\mathscr{F}_2$. We say they are cross $t$-intersecting families. Moreover, we say they are trivial if each member of them contains a fixed $t$-dimensional totally isotropic subspace. In this paper, we show that cross $t$-intersecting families with maximum product of sizes are trivial. We also describe the structure of non-trivial $t$-intersecting families with maximum product of sizes., Comment: Some typos corrected, a reference added, some details of proof added. arXiv admin note: substantial text overlap with arXiv:2201.08084

Denote the collection of all $k$-flats in $AG(n,\mathbb{F}_q)$ by $\mathscr{M}(k,n)$. Let $\mathscr{F}_1\subset\mathscr{M}(k_1,n)$ and $\mathscr{F}_2\subset\mathscr{M}(k_2,n)$ satisfy $\dim(F_1\cap F_2)\ge t$ for any $F_1\in\mathscr{F}_1$ and $F_2\in\mathscr{F}_2$. We say they are cross $t$-intersecting families. Moreover, we say they are trivial if each member of them contains a fixed $t$-flats in $AG(n,\mathbb{F}_q)$. In this paper, we show that cross $t$-intersecting families with maximum product of sizes are trivial. We also describe the structure of non-trivial $t$-intersecting families with maximum product of sizes., Comment: Some typos are corrected

Let $V$ be an $n$-dimensional vector space over the finite field $\mathbb{F}_q$, and ${V\brack k}$ denote the family of all $k$-dimensional subspaces of $V$. The families $\mathcal{F}_1\subseteq{V\brack k_1},\mathcal{F}_2\subseteq{V\brack k_2},\ldots,\mathcal{F}_r\subseteq{V\brack k_r}$ are said to be $r$-cross $t$-intersecting if $\dim(F_1\cap F_2\cap\cdots\cap F_r)\geq t$ for all $F_i\in\mathcal{F}_i,\ 1\leq i\leq r.$ The $r$-cross $t$-intersecting families $\mathcal{F}_1$, $\mathcal{F}_2,\ldots,\mathcal{F}_r$ are said to be non-trivial if $\dim(\cap_{1\leq i\leq r}\cap_{F\in\mathcal{F}_i}F)

We determine the diameter of every connected component of the complement of the power graph and the enhanced power graph of a finite group, which completely answers two questions by Peter J. Cameron., Comment: This paper has been accepted by the journal Ars Mathematica Contemporanea

For positive integers $n,r,k$ with $n\ge r$ and $k\ge2$, a set $\{(x_1,y_1),(x_2,y_2),\dots,(x_r,y_r)\}$ is called a $k$-signed $r$-set on $[n]$ if $x_1,\dots,x_r$ are distinct elements of $[n]$ and $y_1\dots,y_r\in[k]$. We say a $t$-intersecting family consisting of $k$-signed $r$-sets on $[n]$ is trivial if each member of this family contains a fixed $k$-signed $t$-set. In this paper, we determine the structure of large maximal non-trivial $t$-intersecting families. In particular, we characterize the non-trivial $t$-intersecting families with maximum size for $t\ge2$, extending a Hilton-Milner-type result for signed sets given by Borg.

Let $V$ be an $(n+\ell)$-dimensional vector space over a finite field, and $W$ a fixed $\ell$-dimensional subspace of $V$. Write ${V\brack n,0}$ to be the set of all $n$-dimensional subspaces $U$ of $V$ satisfying $\dim(U\cap W)=0$. A family $\mathcal{F}\subseteq{V\brack n,0}$ is $t$-intersecting if $\dim(A\cap B)\geq t$ for all $A,B\in\mathcal{F}$. A $t$-intersecting family $\mathcal{F}\subseteq{V\brack n,0}$ is called non-trivial if $\dim(\cap_{F\in\mathcal{F}}F)

Using the two way distance, we introduce the concepts of weak metric dimension of a strongly connected digraph $\Gamma$. We first establish lower and upper bounds for the number of arcs in $\Gamma$ by using the diameter and weak metric dimension of $\Gamma$, and characterize all digraphs attaining the lower or upper bound. Then we study a digraph with weak metric dimension $1$ and classify all vertex-transitive digraphs having weak metric dimension $1$. Finally, all digraphs of order $n$ with weak metric dimension $n-1$ or $n-2$ are determined.

Let $\mathscr{P}$ be a symplectic polar space over a finite field $\mathbb{F}_q$, and $\mathscr{P}_m$ denote the set of all $m$-dimensional subspaces in $\mathscr{P}$. We say a $t$-intersecting subfamily of $\mathscr{P}_m$ is trivial if there exists a $t$-dimensional subspace contained in each member of this family. In this paper, we determine the structure of maximum sized non-trivial $t$-intersecting subfamilies of $\mathscr{P}_m$.

Given graphs $G$ and $H$, the generalized Tur\'{a}n number ${\rm 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 ${\rm ex}(CT_n,C_{2l})$ for any $n \ge 3$ and $l\geq2$, where $C_{2l}$ is the cycle of length $2l$ and $CT_n$ is the complete transposition graph which is defined as the Cayley graph on the symmetric group ${\rm S}_n$ with respect to the set of all transpositions of ${\rm S}_n$., Comment: 16 pages, 1 figure

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., Comment: 15 pages

Let $V$ be an $n$-dimensional vector space over a finite field $\mathbb{F}_q$. In this paper we describe the structure of maximal non-trivial $t$-intersecting families of $k$-dimensional subspaces of $V$ with large size. We also determine the non-trivial $t$-intersecting families with maximum size. In the special case when $t=1$ our result gives rise to the well-known Hilton-Milner Theorem for vector spaces., Comment: 26 pages

A subset $C$ of the vertex set of a graph $\Gamma$ is called a perfect code of $\Gamma$ if every vertex of $\Gamma$ is at distance no more than one to exactly one vertex in $C$. Let $A$ be a finite abelian group and $T$ a square-free subset of $A$. The Cayley sum graph of $A$ with respect to the connection set $T$ is a simple graph with $A$ as its vertex set, and two vertices $x$ and $y$ are adjacent whenever $x+y\in T$. A subgroup of $A$ is said to be a subgroup perfect code of $A$ if the subgroup is a perfect code of some Cayley sum graph of $A$. In this paper, we give some necessary and sufficient conditions for a subset of $A$ to be a perfect code of a given Cayley sum graph of $A$. We also characterize all subgroup perfect codes of $A$., Comment: 13 pp

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.

A weakly distance-regular digraph is thick if its attached scheme is regular. In this paper, we show that each commutative thick weakly distance-regular digraph has a thick weakly distance-regular subdigraph such that the corresponding quotient digraph falls into six families of thick weakly distance-regular digraphs up to isomorphism.

Let $V$ be an $n$-dimensional vector space over the finite field $\mathbb{F}_q$. Suppose that $\mathscr{F}$ is an intersecting family of $m$-dimensional subspaces of $V$. The covering number of $\mathscr{F}$ is the minimum dimension of a subspace of $V$ which intersects all elements of $\mathscr{F}$. In this paper, we give the tight upper bound for the size of $\mathscr{F}$ whose covering number is $m$, and describe the structure of $\mathscr{F}$ which reaches the upper bound. Moreover, we determine the structure of an maximum intersecting family of singular linear space with the maximum covering number., Comment: 8 pages

We classify certain non-symmetric commutative association schemes. As an application, we determine all the primitive weakly distance-regular circulant digraphs., Comment: 11 pages

The generalized Tur\'{a}n number ${\rm 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\'{a}n number ${\rm 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 ${\rm ex}(J(n;k,k+1),C_{2r})$ with any fixed $k\in\mathbb{Z}^+$ and any $n\in\mathbb{Z}^+$ with $n\geq 2k+1.$ We also give an upper bound for ${\rm ex}(J(2k+1;k,k+1),C_{2r})$ with any $k\in\mathbb{Z}^+,$ where $J(2k+1;k,k+1)$ is known as doubled Odd graph $\widetilde{O}_{k+1}.$ This bound induces that the number of edges in any $C_{2r}$-free subgraph of $\widetilde{O}_{k+1}$ is $o(e(\widetilde{O}_{k+1}))$ for $r\geq 6,$ which also implies a Ramsey-type result., Comment: 14 pages, 1 figure

Let $\Gamma$ be a graph with vertex set $V(\Gamma)$. A subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$ if $C$ is an independent set of $\Gamma$ and every vertex in $V(\Gamma)\setminus C$ is adjacent to exactly one vertex in $C$. A subset $C$ of a group $G$ is called a perfect code of $G$ if there exists a Cayley graph of $G$ which admits $C$ as a perfect code. A group $G$ is said to be code-perfect if every proper subgroup of $G$ is a perfect code of $G$. In this paper we prove that a group is code-perfect if and only if it has no elements of order $4$. We also prove that a proper subgroup $H$ of an abelian group $G$ is a perfect code of $G$ if and only if the Sylow $2$-subgroup of $H$ is a perfect code of the Sylow $2$-subgroup of $G$. This reduces the problem of determining when a given subgroup of an abelian group is a perfect code to the case of abelian $2$-groups. Finally, we determine all subgroup perfect codes in any generalized quaternion group., Comment: This is the final version to be published in SIAM Journal on Discrete Mathematics, 18 pp

Guo and Xu determined the maximum size of intersecting families over finite affine spaces and showed that any family reaches maximum size must be trivial. In this paper, we characterize non-trivial intersecting family with maximum size., Comment: 15 pages

The power graph $\Gamma_G$ of a finite group $G$ is the graph with the vertex set $G$, where two distinct elements are adjacent if one is a power of the other. An $L(2, 1)$-labeling of a graph $\Gamma$ is an assignment of labels from nonnegative integers to all vertices of $\Gamma$ such that vertices at distance two get different labels and adjacent vertices get labels that are at least $2$ apart. The lambda number of $\Gamma$, denoted by $\lambda(\Gamma)$, is the minimum span over all $L(2, 1)$-labelings of $\Gamma$. In this paper, we obtain bounds for $\lambda(\Gamma_G)$, and give necessary and sufficient conditions when the bounds are attained. As applications, we compute the exact value of $\lambda(\Gamma_G)$ if $G$ is a dihedral group, a generalized quaternion group, a $\mathcal{P}$-group or a cyclic group of order $pq^n$, where $p$ and $q$ are distinct primes and $n$ is a positive integer., Comment: 13 pages, 1 figure

In this paper, we study commutative weakly distance-regular digraphs whose attached association schemes are regular, and give a characterization of mixed arcs. As an application, we classify such digraphs of diameter 2., Comment: This paper has been withdrawn by the author because the result of this paper has been added in the paper 2003.08053

The generalized $k$-connectivity $\kappa_{k}(G)$ of a graph $G$, which was introduced by Chartrand et al.(1984) is a generalization of the concept of vertex connectivity. Let $G$ and $H$ be nontrivial connected graphs. Recently, Li et al. gave a lower bound for the generalized $3$-connectivity of the Cartesian product graph $G \square H$ and proposed a conjecture for the case that $H$ is $3$-connected. In this paper, we give two different forms of lower bounds for the generalized $3$-connectivity of Cartesian product graphs. The first lower bound is stronger than theirs, and the second confirms their conjecture.

Let $\mathbb{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. Using matrix representation and the inner rank of a matrix, we study the intersection, join, dimension formula and dual subspaces on vector subspaces of $\mathbb{Z}^n_{p^s}$. Based on these results, we investigate the Grassmann graph $G_{p^s}(n,m)$ over $\mathbb{Z}_{p^s}$. $G_{p^s}(n,m)$ is a connected vertex-transitive graph, and we determine its valency, clique number and maximum cliques. Finally, we characterize the automorphisms of $G_{p^s}(n,m)$., Comment: 25 pages

A weakly distance-regular digraph is 3-equivalenced if its attached association scheme is 3-equivalenced. In this paper, we classify the family of such digraphs under the assumption of the commutativity., Comment: The main theorem of this paper can be proved by other paper's result easily

In 2011, Li et al. \cite{LLL} obtained an upper bound of the strong rainbow connection number of an $r$-dimensional undirected toroidal mesh. In this paper, this bound is improved. As a result, we give a negative answer to their problem., Comment: 9 pages, 3 figures

The {\em 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 {\em $\Gamma$-optimal} if $G$ has order $\Theta(\Gamma)$. We say that $\Gamma$ is {\em power-critical} if its order equals 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., Comment: 12 pages, 1 figure

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 distanceregular digraphs of valency 3 are completely determined.

A weakly distance-regular digraph is quasi-thin if the maximum value of its intersection numbers is 2. In this paper, we focus on commutative quasi-thin weakly distance-regular digraphs, and classify such digraphs with valency more than 3. As a result, this family of digraphs are completely determined., Comment: arXiv admin note: substantial text overlap with arXiv:1606.03521

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 or a generalized quaternion group., Comment: 11 pages

A weakly distance-regular digraph is quasi-thin if the maximum value of its intersection numbers is 2. In this paper, we show that the valency of any commutative quasi-thin weakly distance-regular digraph is at most 6., Comment: This paper has been withdrawn by the author because the result of this paper has been added in another paper

For a finite noncyclic group $G$, let $\Cyc(G)$ be a set of elements $a$ of $G$ such that $\langle a,b\rangle$ is cyclic for each $b$ of $G$. The noncyclic graph of $G$ is a graph with the vertex set $G\setminus \Cyc(G)$, having an edge between two distinct vertices $x$ and $y$ if $\langle x, y\rangle$ is not cyclic. In this paper, we classify all finite noncyclic groups whose noncyclic graphs are $K_{1,n}$-free, where $3\leq n\leq 6$., Comment: 10 pages

The power graph $\Gamma_G$ of a finite group $G$ is the graph whose vertex set is the group, two distinct elements being adjacent if one is a power of the other. In this paper, we classify the finite groups whose power graphs have (non)orientable genus two., Comment: 17 pages, 7 figures

Let $G$ be a finite non-abelian group. The non-commuting graph $\Gamma_G$ of $G$ has the vertex set $G\setminus Z(G)$ and two distinct vertices $x$ and $y$ are adjacent if $xy\ne yx$, where $Z(G)$ is the center of $G$. We prove that the rainbow $2$-connectivity of $\Gamma_G$ is $2$. In particular, the rainbow connection number of $\Gamma_G$ is $2$. Moreover, for any positive integer $k$, we prove that there exist infinitely many non-abelian groups $G$ such that the rainbow $k$-connectivity of $\Gamma_G$ is $2$., Comment: 8 pages

Suzuki (2004) [7] classified thin weakly distance-regular digraphs and pro- posed the project to classify weakly distance-regular digraphs of valency 3. The case of girth 2 was classified by the third author (2004) [9] under the assumption of the commutativity. In this paper, we continue this project and classify these digraphs with girth more than 2 and two types of arcs.

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., Comment: 10 pages, 5 figures, accepted by Graphs and Combinatorics on July 2015

For any positive integer $k$, let $\mathcal{G}_k$ denote the set of finite groups $G$ such that all Cayley graphs ${\rm Cay}(G,S)$ are integral whenever $|S|\le k$. Est${\rm \acute{e}}$lyi and Kov${\rm \acute{a}}$cs \cite{EK14} classified $\mathcal{G}_k$ for each $k\ge 4$. In this paper, we characterize the finite groups each of whose cubic Cayley graphs is integral. Moreover, the class $\mathcal{G}_3$ is characterized. As an application, the classification of $\mathcal{G}_k$ is obtained again, where $k\ge 4$., Comment: 11 pages, accepted by Journal of Algebra and its Applications on June 2015

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.

A graph is called a pseudo-core if every endomorphism is either an automorphism or a colouring. In this paper, we show that every Grassmann graph $J_q(n,m)$ is a pseudo-core. Moreover, the Grassmann graph $J_q(n,m)$ is a core whenever $m$ and $n-m+1$ are not relatively prime, and $J_q(2pk-2, pk-1)$ is a core whenever $p,k\geq 2$., Comment: 8 pages

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

In [H. Suzuki, Association schemes with multiple $Q$-polynomial structures, J. Algebraic Combin. 7 (1998) 181-196], 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., Comment: 8 pages