On extensions of exceptional strongly regular graphs with eigenvalue 3

The study of distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with eigenvalue 3 was initiated by Makhnev. In particular, he reduced these graphs to graphs in which neighborhoods of vertices are exceptional graphs or pseudogeometric graphs for pG _s?3(s, t). Makhnev and Paduchikh found parameters of exceptional graphs (see the proposition). In the present paper, we study amply regular graphs in which neighborhoods of vertices are exceptional strongly regular graphs with nonprincipal eigenvalue 3 and parameters from conditions 3–6 of the Proposition.     

On automorphisms of distance-regular graphs with intersection arrays {2<Emphasis Type="Italic">r</Emphasis> + 1, 2<Emphasis Type="Italic">r</Emphasis> − 2, 1; 1, 2, 2<Emphasis Type="Italic">r</Emphasis> + 1}

Let Γ be an antipodal graph with intersection array {2r+1, 2r?2, 1; 1, 2, 2r+1}, where 2r(r + 1) ≤ 4096. If 2r + 1 is a prime power, then Mathon’s scheme provides the existence of an arc-transitive graph with this intersection array. Note that 2r + 1 is not a prime power only for r ∈ {7, 17, 19, 22, 25, 27, 31, 32, 37, 38, 42, 43}. We study automorphisms of hypothetical distance-regular graphs with the specified values of r. The cases r ∈ {7, 17, 19} were considered earlier. We prove that, if Γ is a vertex-symmetric graph with intersection array {2r + 1, 2r ? 2, 1; 1, 2, 2r +1}, 2r + 1 is not a prime power, and r ≤ 43, then r = 25, 27, or 31.     

Distance-Regular Shilla Graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>2</Subscript> = <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript>

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ₁ equal to a₃. For a Shilla graph, let us put a = a₃ and b = k/a. It is proved in this paper that a Shilla graph with b₂ = c₂ and noninteger eigenvalues has the following intersection array:

$$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$

If Γ is a Q-polynomial Shilla graph with b₂ = c₂ and b = 2r, then the graph Γ has intersection array

$$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$

and, for any vertex u in Γ, the subgraph Γ₃(u) is an antipodal distance-regular graph with intersection array

$$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$

The Shilla graphs with b₂ = c₂ and b = 4 are also classified in the paper.

     

Distance-regular graphs of large diameter that are completely regular clique graphs

A connected graph is said to be a completely regular clique graph with parameters (s, c), \(s, c \in {\mathbb {N}}\), if there is a collection \(\mathcal {C}\) of completely regular cliques of size \(s+1\) such that every edge is contained in exactly c members of \(\mathcal {C}\). It is known that many families of distance-regular graphs are completely regular clique graphs. In this paper, we determine completely regular clique graph structures, i.e., the choices of \(\mathcal {C}\), of all known families of distance-regular graphs with unbounded diameter. In particular, we show that all distance-regular graphs in this category are completely regular clique graphs except the Doob graphs, the twisted Grassmann graphs and the Hermitean forms graphs. We also determine parameters (s, c); however, in a few cases we determine only s and give a bound on the value c. Our result is a generalization of a series of works by J. Hemmeter and others who determined distance-regular graphs in this category that are bipartite halves of bipartite distance-regular graphs.     

Arc-transitive distance-regular covers of cliques with <Emphasis Type="Italic">λ</Emphasis> = µ

We study antipodal distance-regular graphs of diameter 3 such that their automorphism group acts transitively on the set of pairs (a, b), where {a, b} is an edge of the graph. Since the automorphism group of such graphs acts 2-transitively on the set of antipodal classes, the classification of 2-transitive permutation groups can be used. We classify arc-transitive distance-regular graphs of diameter 3 in which any two vertices at distance at most two have exactly µ common neighbors.     

The spectral excess theorem for distance-regular graphs having distance-<Emphasis Type="Italic">d</Emphasis> graph with fewer distinct eigenvalues

Let \(\Gamma \) be a distance-regular graph with diameter d and Kneser graph \(K=\Gamma _d\), the distance-d graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when K has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.     

Distance mean-regular graphs

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let \(\Gamma \) be a graph with vertex set V, diameter D, adjacency matrix \(\varvec{A}\), and adjacency algebra \(\mathcal{A}\). Then, \(\Gamma \) is distance mean-regular when, for a given \(u\in V\), the averages of the intersection numbers \(p_{ij}^h(u,v)=|\Gamma _i(u)\cap \Gamma _j(v)|\) (number of vertices at distance i from u and distance j from v) computed over all vertices v at a given distance \(h\in \{0,1,\ldots ,D\}\) from u, do not depend on u. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of \(\Gamma \) and, hence, they generate a subalgebra of \(\mathcal{A}\). Some other algebras associated to distance mean-regular graphs are also characterized.     

Strongly regular locally <Emphasis Type="Italic">GQ</Emphasis>(4,<Emphasis Type="Italic">t</Emphasis>)-graphs

Amply regular with parameters (v, k, λ, μ) we call an undirected graph with v vertices in which the degrees of all vertices are equal to k, every edge belongs to λ triangles, and the intersection of the neighborhoods of every pair of vertices at distance 2 contains exactly μ vertices. An amply regular diameter 2 graph is called strongly regular. We prove the nonexistence of amply regular locally GQ(4,t)-graphs with (t,μ) = (4, 10) and (8, 30). This reduces the classification problem for strongly regular locally GQ(4,t)-graphs to studying locally GQ(4, 6)-graphs with parameters (726, 125, 28, 20).     

On the Maximum Weight of a Sparse Connected Graph of Given Order and Size

The weight of an edge of a graph is defined to be the sum of degrees of vertices incident to the edge. The weight of a graph G is the minimum of weights of edges of G. Jendrol’ and Schiermeyer (Combinatorica 21:351–359, 2001) determined the maximum weight of a graph having n vertices and m edges, thus solving a problem posed in 1990 by Erd?s. The present paper is concerned with a modification of the mentioned problem, in which involved graphs are connected and of size \(m\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}\lceil n/2\rceil \\ 2\end{array}}\right) \).     

On the Metric Dimension of Imprimitive Distance-Regular Graphs

A resolving set for a graph \({\Gamma}\) is a collection of vertices S, chosen so that for each vertex v, the list of distances from v to the members of S uniquely specifies v. The metric dimension of \({\Gamma}\) is the smallest size of a resolving set for \({\Gamma}\). Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. We show how the metric dimension of an imprimitive distance-regular graph can be related to that of its halved and folded graphs. We also consider infinite families (including Taylor graphs and the incidence graphs of certain symmetric designs) where more precise results are possible.     

Classification of amply regular graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>1</Subscript> = 6

An undirected graph with v vertices in which the degrees of all vertices are equal to k, each edge is contained in exactly λ triangles, and the intersection of the neighborhoods of any two vertices at distance 2 contains exactly µ vertices is called amply regular with parameters (v, k, λ, µ). We complete the classification of amply regular graphs with b ₁ = 6, where b ₁ = k ? λ ? 1.     

On automorphisms of a distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}

Prime divisors of orders of automorphisms and their fixed-point subgraphs are studied for a hypothetical distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}. It is shown that there are no arc-transitive distance-regular graphs with intersection array {35, 32, 1; 1, 4, 35}.     

On the intersection graph of a finite group

For a finite group G, the intersection graph of G which is denoted by Γ(G) is an undirected graph such that its vertices are all nontrivial proper subgroups of G and two distinct vertices H and K are adjacent when H ∩ K ≠ 1. In this paper we classify all finite groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of Aut(Γ(G)).     

Relaxed Locally Identifying Coloring of Graphs

A locally identifying coloring (lid-coloring) of a graph is a proper vertex-coloring such that the sets of colors appearing in the closed neighborhoods of any pair of adjacent vertices having distinct neighborhoods are distinct. Our goal is to study a relaxed locally identifying coloring (rlid-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessarily proper. We denote by \(\chi _{rlid}(G)\) the minimum number of colors used in a relaxed locally identifying coloring of a graph G. In this paper, we prove that the problem of deciding that \(\chi _{rlid}(G)=3\) for a 2-degenerate planar graph G is NP-complete and for a bipartite graph G is polynomial. We give several bounds of \(\chi _{rlid}(G)\) for different families of graphs and construct new graphs for which these bounds are tight. We also compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph G (\(\chi _{lid}(G)\)), the size of a minimum identifying code of G (\(\gamma _{id}(G)\)) and the chromatic number of G (\(\chi (G)\)).     

Graphs with small total rainbow connection number

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that \({\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}}{n - 1} \\2\end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}}n \\2\end{array}} \right) - 1\), and \({\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}}{n - 2} \\2\end{array}} \right) + 2\). Next, we investigate the total rainbow connection numbers of graphs G with |V(G)| = n, diam(G) ≥ 2, and clique number ω(G) = n ? s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.     

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

For a family \(\mathcal {F}\) of graphs, a graph U is induced-universal for \({\mathcal{F}}\) if every graph in \({\mathcal{F}}\) is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most r, which has \(Cn^{\lfloor (r+1)/2\rfloor}\) vertices and \(Dn^{2\lfloor (r+1)/2\rfloor -1}\) edges, where C and D are constants depending only on r. This construction is nearly optimal when r is even in that such an induced-universal graph must have at least cn ^r/2 vertices for some c depending only on r.Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. The construction also extends to multigraphs and directed graphs with bounded degree.     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

Let Γ=(X,R) be a distance-regular graph of diameter d. A parallelogram of length i is a 4-tuple xyzw consisting of vertices of Γ such that ?(x,y)=?(z,w)=1, ?(x,z)=i, and ?(x,w)=?(y,w)=?(y,z)=i?1. A subset Y of X is said to be a completely regular code if the numbers

$\pi_{i,j}=|\Gamma_{j}(x)\cap Y|\quad (i,j\in \{0,1,\ldots,d\})$

depend only on i=?(x,Y) and j. A subset Y of X is said to be strongly closed if

$\{x\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y,\mbox{ whenever }u,v\in Y.$

Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let Γ be a parallelogram-free distance-regular graph of diameter d≥4 such that every strongly closed subgraph of diameter two is completely regular. We show that Γ has a strongly closed subgraph of diameter d?1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two is d?2, Γ itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius is d?2.

     

Structural Properties of Word Representable Graphs

Given a word \(w=w_1w_2\cdots w_n\) of length n over an ordered alphabet \(\Sigma _k\), we construct a graph \(G(w)=(V(w), E(w))\) such that V(w) has n vertices labeled \(1, 2,\ldots , n\) and for \(i, j \in V(w)\), \((i, j) \in E(w)\) if and only if \(w_iw_j\) is a scattered subword of w of the form \(a_{t}a_{t+1}\), \(a_t \in \Sigma _k\), for some \(1 \le t \le k-1\) with the ordering \(a_t<a_{t+1}\). A graph is said to be Parikh word representable if there exists a word w over \(\Sigma _k\) such that \(G=G(w)\). In this paper we characterize all Parikh word representable graphs over the binary alphabet in terms of chordal bipartite graphs. It is well known that the graph isomorphism (GI) problem for chordal bipartite graph is GI complete. The GI problem for a subclass of (6, 2) chordal bipartite graphs has been addressed. The notion of graph powers is a well studied topic in graph theory and its applications. We also investigate a bipartite analogue of graph powers of Parikh word representable graphs. In fact we show that for G(w), \(G(w)^{[3]}\) is a complete bipartite graph, for any word w over binary alphabet.