Search

Let G S be the graph obtained by attaching a self-loop at every vertex in S ⊆ V (G) of a simple graph G of order n. In this paper, we explore several new results related to the line graph L (G S) of G S. Particularly, we show that every eigenvalue of L (G S) must be at least - 2 , and relate the characteristic polynomial of the line graph L(G) of G with the characteristic polynomial of the line graph L (G ^) of a self-loop graph G ^ , which is obtained by attaching a self-loop at each vertex of G. Then, we provide some new bounds for the eigenvalues and energy of G S. As one of the consequences, we obtain that the energy of a connected regular complete multipartite graph is not greater than the energy of the corresponding self-loop graph. Lastly, we establish a lower bound of the spectral radius in terms of the first Zagreb index M 1 (G) and the minimum degree δ (G) , as well as proving two Nordhaus–Gaddum-type bounds for the spectral radius and the energy of G S , respectively. [ABSTRACT FROM AUTHOR]

Let G S be a graph with loops obtained from a graph G of order n and loops at S ⊆ V (G). In this paper, we establish a neccesary and sufficient condition on the bipartititeness of a connected graph G and the spectrum Spec (G S) and Spec (G V (G) \ S) . We also prove that for every S ⊆ V (G) , E (G S) ≥ E (G) when G is bipartite. Moreover, we provide an identification of the spectrum of complete graphs K n and complete bipartite graphs K m , n with loops. We characterize any graphs with loops of order n whose eigenvalues are all positive or non-negative, and also any graphs with a few distinct eigenvalues. Finally, we provide some bounds related to G S . [ABSTRACT FROM AUTHOR]

A circular zero-sum flow for a graph G is a function f : E (G) → R \ { 0 } such that for every vertex v, ∑ e ∈ E v f (e) = 0 , where E v is the set of all edges incident with v. If for each edge e, 1 ≤ | f (e) | ≤ r - 1 , where r ≥ 2 is a real number, then f is called a circular zero-sum r-flow. Also, if r is a positive integer and for each edge e, f(e) is an integer, then f is called a zero-sum r-flow. If G has a circular zero-sum flow, then the minimum r ≥ 2 for which G has a circular zero-sum r-flow is called the circular zero-sum flow number of G and is denoted by Φ c (G) . Also, the minimum integer r ≥ 2 for which G has a zero-sum r-flow is called the flow number for G and is denoted by Φ (G) . In this paper, we investigate circular zero-sum r-flows of regular graphs. In particular, we show that if G is k-regular with m edges, then Φ c (G) = 2 for even k and even m, Φ c (G) = 1 + k + 2 k - 2 for even k and odd m, and Φ c (G) ≤ 1 + (k + 1 k - 1) 2 for odd k. It was proved that for every k-regular graph G with k ≥ 3 , Φ (G) ≤ 5 . Here, using circular zero-sum flows, we present a new proof of this result when k ≠ 5 . Finally, we prove that a graph G has a circular zero-sum flow f such that for every edge e, l (e) ≤ f (e) ≤ u (e) , if and only if for every partition of V(G) into three subsets A, B, C, l (A , C) + 2 l (A) ≤ u (B , C) + 2 u (B) , where l(A, C) is the sum of values of l on the edges between A, C, and l(A) is the sum of values of l on the edges with both ends in A (the definitions of u(B, C) and u(B) are analogous). [ABSTRACT FROM AUTHOR]

Let G be a graph whose each component has order at least 3. Let $$s : E(G) \rightarrow {\mathbb {Z}}_k$$ for some integer $$k\ge 2$$ be an improper edge coloring of G (where adjacent edges may be assigned the same color). If the induced vertex coloring $$c : V (G) \rightarrow {\mathbb {Z}}_k$$ defined by $$c(v) = \sum _{e\in E_v} s(e) \text{ in } {\mathbb {Z}}_k,$$ (where the indicated sum is computed in $${\mathbb {Z}}_k$$ and $$E_v$$ denotes the set of all edges incident to v) results in a proper vertex coloring of G, then we refer to such a coloring as an improper twin k-edge coloring. The minimum k for which G has an improper twin k-edge coloring is called the improper twin chromatic index of G and is denoted by $$\chi '_{it}(G)$$ . It is known that $$\chi '_{it}(G)=\chi (G)$$ , unless $$\chi (G) \equiv 2 \pmod 4$$ and in this case $$\chi '_{it}(G)\in \{\chi (G), \chi (G)+1\}$$ . In this paper, we first give a short proof of this result and we show that if G admits an improper twin k-edge coloring for some positive integer k, then G admits an improper twin t-edge coloring for all $$t\ge k$$ ; we call this the monotonicity property. In addition, we provide a linear time algorithm to construct an improper twin edge coloring using at most $$k+1$$ colors, whenever a k-vertex coloring is given. Then we investigate, to the best of our knowledge the first time in literature, the complexity of deciding whether $$\chi '_{it}(G)=\chi (G)$$ or $$\chi '_{it}(G)=\chi (G)+1$$ , and we show that, just like in case of the edge chromatic index, it is NP-hard even in some restricted cases. Lastly, we exhibit several classes of graphs for which the problem is polynomial. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph of order $$n$$ and size $$m$$ . Suppose that $$f:V(G)\rightarrow {\mathbb {N}}$$ is a function such that $$\sum _{v\in V(G)}f(v)=m+n$$ . In this paper we provide a criterion for $$f$$ -choosability of $$G$$ . Using this criterion, it is shown that the choice number of the complete $$k$$ -partite graph $$K_{2,2,\ldots ,2}$$ is $$k$$ , which is a well-known result due to Erdös, Rubin and Taylor. Among other results we study the $$f$$ -choosability of the complete $$k$$ -partite graphs with part sizes at most $$2$$ , when $$f(v)\in \{k-1,k\}$$ , for every vertex $$v\in V(G)$$ . [ABSTRACT FROM AUTHOR]

For a set $${\mathcal{S}}$$ of positive integers, a spanning subgraph F of a graph G is called an $${\mathcal{S}}$$ -factor of G if $${\deg_F(x) \in \mathcal{S}}$$ for all vertices x of G, where deg( x) denotes the degree of x in F. We prove the following theorem on { a, b}-factors of regular graphs. Let r ≥ 5 be an odd integer and k be either an even integer such that 2 ≤ k < r/2 or an odd integer such that r/3 ≤ k < r/2. Then every r-regular graph G has a { k, r- k}-factor. Moreover, for every edge e of G, G has a { k, r- k}-factor containing e and another { k, r- k}-factor avoiding e. [ABSTRACT FROM AUTHOR]

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ − 1)-flow. We denote the minimum flow number of G by Λ( G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ( G ∨ H) ⩽ 3 except two cases: (i) One of the graphs G and H is K and the other is 1-regular. (ii) H = K and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ( G ∨ H) ⩽ 3. [ABSTRACT FROM AUTHOR]

A Roman dominating function on a graph G = ( V( G), E( G)) is a labelling $${f : V(G)\rightarrow \{0,1,2\}}$$ satisfying the condition that every vertex with label 0 has at least a neighbour with label 2. The Roman domination number γ( G) of G is the minimum of $${\sum_{v \in V(G)}{f(v)}}$$ over all such functions. The Roman bondage number b( G) of G is the minimum cardinality of all sets $${E\subseteq E(G)}$$ for which γ( G \ E) > γ( G). Recently, it was proved that for every planar graph P, b( P) ≤ Δ( P) + 6, where Δ( P) is the maximum degree of P. We show that the Roman bondage number of every planar graph does not exceed 15 and construct infinitely many planar graphs with Roman bondage number equal to 7. [ABSTRACT FROM AUTHOR]

Let R be a ring with unity. The graph Γ( R) is a graph with vertices as elements of R, where two distinct vertices a and b are adjacent if and only if Ra + Rb = R. Let Γ( R) be the subgraph of Γ( R) induced by the non-unit elements of R. Let R be a commutative ring with unity and let J( R) denote the Jacobson radical of R. If R is not a local ring, then it was proved that: In this note we generalize the above results to non-commutative rings and characterize all non-local ring R (not necessarily commutative) whose $\Gamma_2(R)\backslash J(R)$ is a complete n-partite graph. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n such that $\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}$ and $\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}$ are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that a≥ b for i=0,1,..., n. As a consequence, we prove that for any α, 0< α≤1, if q,..., q and μ,..., μ are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then $q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}$. [ABSTRACT FROM AUTHOR]