Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.     

Minimum degree, leaf number and traceability

Let G be a finite connected graph with minimum degree δ. The leaf number L(G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We prove that if δ ? 1/2 (L(G) + 1), then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ? 1/2 (L(G) + 1), then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaViña and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1–16]. For G claw-free, we show that if δ ? 1/2 (L(G) + 1), then G is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.     

On spectral characterizations and embeddings of graphs

The least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than ?2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,…,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E₈. If G is regular with λ(G)>?2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λ_R(H) = sup{λ(G)z.sfnc;HinG; Gregular}. H is an odd circuit, a path, or a complete graph iff λ_R(H)> ?2. For any other line graph H, λ_R(H) = ?2. A similar result holds for complete multipartite graphs.     

On the sum of the Laplacian eigenvalues of a tree

Given an n-vertex graph G=(V,E), the Laplacian spectrum of G is the set of eigenvalues of the Laplacian matrix L=D-A, where D and A denote the diagonal matrix of vertex-degrees and the adjacency matrix of G, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where k∈{1,…,n}. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenkovi? and Gutman [10].     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

On generalized Petersen graphs labeled with a condition at distance two

An L(2,1)-labeling of graph G is an integer labeling of the vertices in V(G) such that adjacent vertices receive labels which differ by at least two, and vertices which are distance two apart receive labels which differ by at least one. The λ-number of G is the minimum span taken over all L(2,1)-labelings of G. In this paper, we consider the λ-numbers of generalized Petersen graphs. By introducing the notion of a matched sum of graphs, we show that the λ-number of every generalized Petersen graph is bounded from above by 9. We then show that this bound can be improved to 8 for all generalized Petersen graphs with vertex order >12, and, with the exception of the Petersen graph itself, improved to 7 otherwise.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

On domination and independent domination numbers of a graph

For a graph G, the definitions of domination number, denoted γ(G), and independent domination number, denoted i(G), are given, and the following results are obtained:Theorem.If G does not have an induced subgraph isomorphic to K_1,3, thenγ(G) = i(G).Corollary 1.For any graph G, γ(L(G))=i(L(G)), where L(G) is the line graph of G. (This extends the result γ(L(T))=i(L(T)), where T is a tree. Hedetniemi and Mitchell, S. E. Conf. Baton Rouge, 1977.)Corollary 2.For any Graph G, γ(M(G))=i(M(G)), where M is the middle graph of G.     

The Laplacian energy of random graphs

Gutman et al. introduced the concepts of energy E(G) and Laplacian energy EL(G) for a simple graph G, and furthermore, they proposed a conjecture that for every graph G, E(G) is not more than EL(G). Unfortunately, the conjecture turns out to be incorrect since Liu et al. and Stevanovi? et al. constructed counterexamples. However, So et al. verified the conjecture for bipartite graphs. In the present paper, we obtain, for a random graph, the lower and upper bounds of the Laplacian energy, and show that the conjecture is true for almost all graphs.     

An interrelation between line graphs,eigenvalues, and matroids

If L(G) is the line graph of G, and A(L(G)), the adjacency matrix of L(G), acts on a vector x, this vector may be thought of as an integral chain of G. The eigenspace of L(G) determines a matroid for G. For the eigenvalue ?2, this matroid has a geometric interpretation, and from this we obtain all eigenvectors corresponding to this eigenvalue. Matroids are normally considered over integral domains, and the results for eigenvectors are generalized to a geometric interpretation for all integral domains. These results are applied to the ring of complex numbers, and strict bounds for the least eigenvalue of a line graph are obtained.     

The energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

Distance-biregular graphs with 2-valent vertices and distance-regular line graphs

A graph G is called distance-regularized if each vertex of G admits an intersection array. It is known that every distance-regularized graph is either distance-regular (DR) or distance-biregular (DBR). Note that DBR means that the graph is bipartite and the vertices in the same color class have the same intersection array. A (k, g)-graph is a k-regular graph with girth g and with the minimum possible number of vertices consistent with these properties. Biggs proved that, if the line graph L(G) is distance-transitive, then G is either K_1,n or a (k, g)-graph. This result is generalized to DR graphs by showing that the following are equivalent: (1) L(G) is DR and G ≠ K_1,n for n ≥ 2, (2) G and L(G) are both DR, (3) subdivision graph S(G) is DBR, and (4) G is a (k, g)-graph. This result is used to show that a graph S is a DBR graph with 2-valent vertices iff S = K_2,′ or S is the subdivision graph of a (k, g)-graph. Let G⁽²⁾ be the graph with vertex set that of G and two vertices adjacent if at distance two in G. It is shown that for a DBR graph G, G⁽²⁾ is two DR graphs. It is proved that a DR graph H without triangles can be obtained as a component of G⁽²⁾ if and only if it is a (k, g)-graph with g ≥ 4.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

Energy of generalized line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. Line graphs play an important role in the study of graph theory. Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. In this paper, we establish relations between the energy of the generalized line graph of a graph G and the Laplacian and signless Laplacian energies of G. We give upper and lower bounds for the energy of generalized line graphs. Finally, we present upper and lower bounds for some special graphs.