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.     

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.     

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.     

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.     

The spectrum of infinite regular line graphs

Let be an infinite -regular graph and its line graph. We consider discrete Laplacians on and , and show the exact relation between the spectrum of and that of . Our method is also applicable to -semiregular graphs, subdivision graphs and para-line graphs.

     

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.     

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.     

Antimagic orientations of disconnected even regular graphs

A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u\in V\left(D\right)$ for a labeling is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2$d$-regular graphs with more than two odd components. We show that every 2$d$-regular graph with $k(3\le k\le 5d+4)$ odd components has an antimagic orientation. And we show that each 2$d$-regular graph with $k(k\ge 5d+5)$ odd components admits an antimagic orientation if each odd component has at least $2x_0+5$ vertices with $x_0=?\frac{k?(5d+4)}{2d?2}?$.     

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.     

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.     

Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)?5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k?2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k?2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.     

Subgroup regular sets in Cayley graphs

Let Γ be a graph with vertex set V, and let a and b be nonnegative integers. A subset C of V is called an $(a,b)$-regular set in Γ if every vertex in C has exactly a neighbors in C and every vertex in $V?C$ has exactly b neighbors in C. In particular, $(0,1)$-regular sets and $(1,1)$-regular sets in Γ are called perfect codes and total perfect codes in Γ, respectively. A subset C of a group G is said to be an $(a,b)$-regular set of G if there exists a Cayley graph of G which admits C as an $(a,b)$-regular set. In this paper we prove that, for any generalized dihedral group G or any group G of order 4p or pq for some primes p and q, if a nontrivial subgroup H of G is a $(0,1)$-regular set of G, then it must also be an $(a,b)$-regular set of G for any $0?a?|H|?1$ and $0?b?|H|$ such that a is even when $|H|$ is odd. A similar result involving $(1,1)$-regular sets of such groups is also obtained in the paper.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.