Star complements and exceptional graphs

Let G be a finite graph of order n with an eigenvalue μ of multiplicity k. (Thus the μ-eigenspace of a (0,1)-adjacency matrix of G has dimension k.) A star complement for μ in G is an induced subgraph G-X of G such that |X|=k and G-X does not have μ as an eigenvalue. An exceptional graph is a connected graph, other than a generalized line graph, whose eigenvalues lie in [-2,∞). We establish some properties of star complements, and of eigenvectors, of exceptional graphs with least eigenvalue −2.     

Co-cliques and star complements in extremal strongly regular graphs

Suppose that the positive integer μ is the eigenvalue of largest multiplicity in an extremal strongly regular graph G. By interlacing, the independence number of G is at most 4μ² + 4μ − 2. Star complements are used to show that if this bound is attained then either (a) μ = 1 and G is the Schläfli graph or (b) μ = 2 and G is the McLaughlin graph.     

Old and new results on algebraic connectivity of graphs

This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors related to a(G)) on trees, on hard problems in graphs and also on the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity.     

Walks and regular integral graphs

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half.Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.     

Further results on the least eigenvalue of connected graphs

In this paper, we identify within connected graphs of order n and size n+k (with and ) the graphs whose least eigenvalue is minimal. It is also observed that the same graphs have the largest spectral spread if n is large enough.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

Some new strongly regular graphs

We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families.     

Packing in regular graphs

A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k² ? 1).     

Star chromatic numbers of graphs

We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou.     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Spectral radius and Hamiltonicity of graphs

Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write K_n-1+v for the complete graph on n-1 vertices together with an isolated vertex, and K_n-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=K_n-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=K_n-1+e.If , then G contains a Hamiltonian path unless G=K_n-1+v.If , then G contains a Hamiltonian cycle unless G=K_n-1+e.     

The largest eigenvalue of unicyclic graphs

Let G be a simple graph. Let λ₁(G) and μ₁(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then

     

The algebraic connectivity of lollipop graphs

Let C_n,g be the lollipop graph obtained by appending a g-cycle C_g to a pendant vertex of a path on n-g vertices. In 2002, Fallat, Kirkland and Pati proved that for and g?4, α(C_n,g)>α(C_n,g-1). In this paper, we prove that for g?4, α(C_n,g)>α(C_n,g-1) for all n, where α(C_n,g) is the algebraic connectivity of C_n,g.     

Energy of unitary Cayley graphs and gcd-graphs

This work is based on ideas of Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009) 1881-1889] on the energy of unitary Cayley graph. For a finite commutative ring R with unity , the unitary Cayley graph of R is the Cayley graph whose vertex set is R and the edge set is {{a,b}:a,b∈Randa-b∈R^×}, where R^× is the group of units of R. We study the eigenvalues of the unitary Cayley graph of a finite commutative ring and some gcd-graphs and compute their energy. Moreover, we obtain the energy for the complement of unitary Cayley graphs.     

Signless Laplacians of finite graphs

We survey properties of spectra of signless Laplacians of graphs and discuss possibilities for developing a spectral theory of graphs based on this matrix. For regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian, and so we consider arbitrary graphs with special emphasis on the non-regular case. The results which we survey (old and new) are of two types: (a) results obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix, (b) results obtained indirectly via line graphs. Among other things, we present eigenvalue bounds for several graph invariants, an interpretation of the coefficients of the characteristic polynomial, a theorem on powers of the signless Laplacian and some remarks on star complements.     

Integral complete 4-partite graphs

A graph G is called integral if all the roots of the characteristic polynomial P(G;x) are integers. In the paper the first known integral complete 4-partite graph K_p1,p2,p3,p4, where p₁<p₂<p₃<p₄, is constructed.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

Connected graphs of fixed order and size with maximal index: Some spectral bounds

The index (or spectral radius) of a simple graph is the largest eigenvalue of its adjacency matrix. For connected graphs of fixed order and size the graphs with maximal index are not yet identified (in the general case). It is known (for a long time) that these graphs are nested split graphs (or threshold graphs). In this paper we use the eigenvector techniques for getting some new (lower and upper) bounds on the index of nested split graphs. Besides we give some computational results in order to compare these bounds.