On the Laplacian spectrum of an infinite graph

In this paper, we introduce the notion of Laplacian spectrum of an infinite countable graph in a different way than in the papers by B. Mohar. We prove some basic properties of this type of spectrum. The approach used is in line with our approach to the limiting spectrum of an infinite graph. The technique of the Laplacian spectrum of finite graphs is essential in this approach.     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

The local spectra of regular line graphs

The local spectrum of a graph G=(V,E), constituted by the standard eigenvalues of G and their local multiplicities, plays a similar role as the global spectrum when the graph is “seen” from a given vertex. Thus, for each vertex i∈V, the i-local multiplicities of all the eigenvalues add up to 1; whereas the multiplicity of each eigenvalue λ of G is the sum, extended to all vertices, of its local multiplicities.In this work, using the interpretation of an eigenvector as a charge distribution on the vertices, we compute the local spectrum of the line graph LG in terms of the local spectrum of the regular graph G it derives from. Furthermore, some applications of this result are derived as, for instance, some results about the number of circuits of LG.     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

Eigenvalues and edge-connectivity of regular graphs

In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than , then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let ρ(d) denote the largest root of x³-(d-3)x²-(3d-2)x-2=0. We show that if the second largest eigenvalue of a d-regular graph G is less than ρ(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than , then G is 3-edge-connected.     

The existence of even regular factors of regular graphs on the number of cut edges

For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.     

Size Ramsey numbers for some regular graphs

P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of K_n,n,n. The result is a generalization of a theorem for K_n,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed.     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

The clique numbers of regular graphs of matrix algebras are finite

Let F be a field, char(F)≠2, and SGL_n(F), where n is a positive integer. In this paper we show that if for every distinct elements x,yS, x+y is singular, then S is finite. We conjecture that this result is true if one replaces field with a division ring.     

Comment on “Kirchhoff index in line,subdivision and total graphs of a regular graph”

Let G$G$ be a connected regular graph. Denoted by t(G)$t\left(G\right)$ and Kf(G)$Kf\left(G\right)$ the total graph and Kirchhoff index of G$G$, respectively. This paper is to point out that Theorem 3.7 and Corollary 3.8 from “Kirchhoff index in line, subdivision and total graphs of a regular graph” [X. Gao, Y.F. Luo, W.W. Liu, Kirchhoff index in line, subdivision and total graphs of a regular graph, Discrete Appl. Math. 160(2012) 560–565] are incorrect, since the conclusion of a lemma is essentially wrong. Moreover, we first show the Laplacian characteristic polynomial of t(G)$t\left(G\right)$, where G$G$ is a regular graph. Consequently, by using Kf(G)$Kf\left(G\right)$, we give an expression on Kf(t(G))$Kf\left(t\left(G\right)\right)$ and a lower bound on Kf(t(G))$Kf\left(t\left(G\right)\right)$ of a regular graph G$G$, which correct Theorem 3.7 and Corollary 3.8 in Gao et al. (2012)  [2].     

The Laplacian polynomial and Kirchhoff index of graphs derived from regular graphs

Let R(G)$R\left(G\right)$ be the graph obtained from G$G$ by adding a new vertex corresponding to each edge of G$G$ and by joining each new vertex to the end vertices of the corresponding edge, and Q(G)$Q\left(G\right)$ be the graph obtained from G$G$ by inserting a new vertex into every edge of G$G$ and by joining by edges those pairs of these new vertices which lie on adjacent edges of G$G$. In this paper, we determine the Laplacian polynomials of R(G)$R\left(G\right)$ and Q(G)$Q\left(G\right)$ of a regular graph G$G$; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs.     

A note on a conjecture on maximum matching in almost regular graphs

Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G)−δ(G)≤1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

Dominating and large induced trees in regular graphs

Recently Chen et al. [Tree domination in graphs, Ars Combin. 73 (2004) 193-203] asked for characterizations of the class of graphs and the class of regular graphs that have an induced dominating tree, i.e. for which there exists a dominating set that induces a tree.We give a somewhat negative answer to their question by proving that the corresponding decision problems are NP-complete. Furthermore, we prove essentially best-possible lower bounds on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.Finally, we give a forbidden induced subgraph condition for the existence of induced dominating trees.     

Some graphs determined by their spectra

Let denote the graph obtained by attaching m pendent edges to a vertex of complete graph K_n-m, and U_n,p the graph obtained by attaching n-p pendent edges to a vertex of C_p. In this paper, we first prove that the graph and its complement are determined by their adjacency spectra, and by their Laplacian spectra. Then we prove that U_n,p is determined by its Laplacian spectrum, as well as its adjacency spectrum if p is odd, and find all its cospectral graphs for U_n,4.     

Signless Laplacian spectral characterization of 4-rose graphs

A rose graph with p petals (or p-rose graph) is a graph obtained by taking p cycles with just a vertex in common. In this paper, we prove that all 4-rose graphs are determined by their signless Laplacian spectra.     

Signless Laplacian spectral characterization of line graphs of T-shape trees

A T-shape tree is a tree with exactly one vertex of maximum degree 3. The line graphs of the T-shape trees are triangles with a hanging path at each vertex. Let C_a,b,c be such a graph, where a, b and c are the lengths of the paths. In this paper, we show that line graphs of T-shape trees, with the sole exception of C_a,a,2a+1, are determined by the spectra of their signless Laplacian matrices. For the graph C_a,a,2a+1 we identify the unique non-isomorphic graph sharing the same signless Laplacian characteristic polynomial.