Search

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]

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]