Search

Let F 1 and F 2 be two disjoint graphs. The union F 1 ∪ F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) , and the join F 1 + F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) ∪ { x y | x ∈ V (F 1) and y ∈ V (F 2) } . In this paper, we present a characterization to (P 5 , K 1 ∪ K 3) -free graphs, prove that χ (G) ≤ 2 ω (G) - 1 if G is (P 5 , K 1 ∪ K 3) -free. Based on this result, we further prove that χ (G) ≤ max { 2 ω (G) , 15 } if G is a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph. We also construct a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph G with χ (G) = 2 ω (G) . [ABSTRACT FROM AUTHOR]

We consider two recent conjectures made by Harrington, Henninger-Voss, Karhadkar, Robinson and Wong concerning relationships between the sum index, difference index and exclusive sum number of graphs. One conjecture posits an exact relationship between the first two invariants; we show that in fact the predicted value may be arbitrarily far from the truth in either direction. In the process we establish some new bounds on both the sum and difference index. The other conjecture, that the exclusive sum number can exceed the sum index by an arbitrarily large amount, follows from known, but non-constructive, results; we give an explicit construction demonstrating it. Simultaneously with the first preprint of this paper appearing, Harrington et al. updated their preprint with two counterexamples to the first conjecture; however, their counterexamples only give a discrepancy of 1, and only in one direction. They therefore modified the conjecture from an equality to an inequality; our results show that this is still false in general. [ABSTRACT FROM AUTHOR]

Let G be a finite abelian group, written additively, and H a subgroup of G. The subgroup sum graph Γ G , H is the graph with vertex set G, in which two distinct vertices x and y are joined if x + y ∈ H \ { 0 } . These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the prime sum graphs, in the case where H = p G for some prime number p. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph Γ G , H + , which we refer to as the extended subgroup sum graph, in which x and y are joined if x + y ∈ H : the subgroup sum is obtained by removing from this graph the partial matching of edges having the form { x , - x } when 2 x ≠ 0 . We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs. [ABSTRACT FROM AUTHOR]

An inclusive distance vertex irregular labeling of a graph G is an assignment of positive integers { 1 , 2 , ... , k } to the vertices of G such that for every vertex the sum of numbers assigned to its closed neighborhood is different. The minimum number k for which exists an inclusive distance vertex irregular labeling of G is denoted by dis ^ (G) . In this paper we prove that for a simple graph G on n vertices in which no two vertices have the same closed neighborhood dis ^ (G) ≤ n 2 . [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we give counterexamples to the lower bound of χ la (G ∨ O 2) that was obtained in [Local antimagic vertex coloring of a graph, Graphs Combin. 33:275–285 (2017)]. A sharp lower bound of χ la (G ∨ O n) and sufficient conditions for the given lower bound to be attained are obtained. Moreover, we settled Theorem 2.15 and solved Problem 3.3 in the affirmative. We also completely determined the local antimagic chromatic number of complete bipartite graphs. [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]

A group distance magic labeling or a $${\mathcal{G}}$$ -distance magic labeling of a graph G = ( V, E) with $${|V | = n}$$ is a bijection f from V to an Abelian group $${\mathcal{G}}$$ of order n such that the weight $${w(x) = \sum_{y\in N_G(x)}f(y)}$$ of every vertex $${x \in V}$$ is equal to the same element $${\mu \in \mathcal{G}}$$ , called the magic constant. In this paper we will show that if G is a graph of order n = 2(2 k + 1) for some natural numbers p, k such that $${\deg(v)\equiv c \mod {2^{p+1}}}$$ for some constant c for any $${v \in V(G)}$$ , then there exists a $${\mathcal{G}}$$ -distance magic labeling for any Abelian group $${\mathcal{G}}$$ of order 4 n for the composition G[ C]. Moreover we prove that if $${\mathcal{G}}$$ is an arbitrary Abelian group of order 4 n such that $${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$$ for some Abelian group $${\mathcal{A}}$$ of order n, then there exists a $${\mathcal{G}}$$ -distance magic labeling for any graph G[ C], where G is a graph of order n and n is an arbitrary natural number. [ABSTRACT FROM AUTHOR]

A proper edge k-colouring of a graph $$G=(V,E)$$ is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge k-colouring, or nsd k-colouring for short, is a proper edge k-colouring such that $$\sum _{e\ni u}c(e)\ne \sum _{e\ni v}c(e)$$ for every edge uv of G. We denote by $$\chi '_{\Sigma }(G)$$ the neighbour sum distinguishing index of G, which is the least integer k such that an nsd k-colouring of G exists. By definition at least maximum degree, $$\Delta (G)$$ colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$ for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$ and $$\Delta (G) \ge 6$$ . [ABSTRACT FROM AUTHOR]

Suppose that G is a graph and $${f: V (G) \rightarrow \mathbb{N}}$$ is a labeling of the vertices of G. Let S( v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if $${S(u) \neq S(v),}$$ for every pair of adjacent vertices u and v. Also, for each vertex $${v \in V(G),}$$ let L( v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that $${f(v) \in L(v),}$$ for each $${v \in V(G).}$$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η( G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with $${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too. [ABSTRACT FROM AUTHOR]

A labeling of a graph is a mapping that carries some sets of graph elements into numbers (usually the positive integers). An $$(a,d)$$ -edge-antimagic total labeling of a graph $$G(V,E)$$ is a one-to-one mapping $$f$$ from $$V(G)\cup E(G)$$ onto the set $$\{1,2,\dots , |V(G)|+|E(G)|\}$$ , such that the set of all the edge-weights, $$wt_f (uv) = f(u) +f(uv)+f(v)$$ , $$uv\in E(G)$$ , forms an arithmetic sequence starting from $$a$$ and having a common difference $$d$$ . Such a labeling is called super if the smallest possible labels appear on the vertices. In this paper we study the existence of such labelings for circulant graphs. [ABSTRACT FROM AUTHOR]

For a graph $$X$$ with at most one isolated vertex and without isolated edges, a product-irregular labeling $$\omega :E(X)\rightarrow \{1,2,\ldots ,s\}$$ , first defined by Anholcer in 2009, is a labeling of the edges of $$X$$ such that for any two distinct vertices $$u$$ and $$v$$ of $$X$$ the product of labels of the edges incident with $$u$$ is different from the product of labels of the edges incident with $$v$$ . The minimal $$s$$ for which there exist a product irregular labeling is called the product irregularity strength of $$X$$ and is denoted by $$ps(X)$$ . In this paper it is proved that $$ps(X)\le |V(X)|-1$$ for any graph $$X$$ with more than $$3$$ vertices. Moreover, the connection between the product irregularity strength and the multidimensional multiplication table problem is given, which is especially expressed in the case of the complete multipartite graphs. [ABSTRACT FROM AUTHOR]

A k-ranking of a graph G is a function $$f: V(G) \rightarrow \left\{ 0, 1, \ldots , k-1 \right\} $$ such that if $$f(u)=f(v)$$ for any $$u, v \in V(G)$$ , then on every uv path in G, there exists a vertex w with $$f(w) > f(u)$$ . The optimality of a k-ranking is measured in terms of the $$l_{\infty }$$ norm of the sequence of labels produced by the k-ranking (max optimality). We study the optimality of rankings of graphs under all $$l_p$$ norms. In particular, we show that there exist graphs where no max-optimal rankings are $$l_p$$ optimal for any non-negative finite real number p, and vice versa. [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]

The k-coprime graph of order n is the graph with vertex set { k , k + 1 , ... , k + n - 1 } in which two vertices are adjacent if and only if they are coprime. We characterize Hamiltonian k-coprime graphs. As a particular case, two conjectures by Tout et al. (Natl Acad Sci Lett 11:365–368, 1982) and by Schroeder (Graph Comb 38:119–140, 2019) on prime labeling of 2-regular graphs follow. A prime labeling of a graph with n vertices is a labeling of its vertices with distinct integers from { 1 , 2 , ... , n } in such a way that the labels of any two adjacent vertices are relatively prime. [ABSTRACT FROM AUTHOR]

After publication of the research article named above, the author discovered an error in the proof of the main theorem that has a major impact on the stated results. This erratum adds an additional restriction to the statements of Lemma 7 and Theorem 1 from the original article that greatly reduces the scope of those results. [ABSTRACT FROM AUTHOR]

A graph G is prime if the vertices can be distinctly labeled with the integers 1,2,...,|V(G)| so that adjacent vertices have relatively prime labels. We show that every cubic bipartite graph is prime except K3,3, which implies a number of other results. We also provide evidence to support a conjectured classification for the primality of 2-regular graphs. [ABSTRACT FROM AUTHOR]

Let $$G=(V,E)$$ be a graph of order $$n$$ . A distance magic labeling of $$G$$ is a bijection $$\ell :V\rightarrow \{1,\ldots ,n\}$$ for which there exists a positive integer $$k$$ such that $$\sum _{x\in N(v)}\ell (x)=k$$ for all $$v\in V $$ , where $$N(v)$$ is the neighborhood of $$v$$ . We introduce a natural subclass of distance magic graphs. For this class we show that it is closed for the direct product with regular graphs and closed as a second factor for lexicographic product with regular graphs. In addition, we characterize distance magic graphs among direct product of two cycles. [ABSTRACT FROM AUTHOR]

A distance magic labeling of a graph $$G=(V,E)$$ of order $$n$$ is a bijection $$l :V \rightarrow \{1, 2,\ldots , n\}$$ with the property that there is a positive integer $$k$$ (called magic constant) such that $$w(x) = k$$ for every $$x \in V$$ . If a graph $$G$$ admits a distance magic labeling, then we say that $$G$$ is a distance magic graph. In the case of non-regular graph $$G$$ , the problem of determining whether there is a distance magic labeling of the lexicographic product $$G\circ C_4$$ was posted in Arumugam et al. (J Indonesian Math Soc 11-26, ). We give necessary and sufficient conditions for the graphs $$K_{m,n}\circ C_4$$ to be distance magic. We also show that the product $$C^{(t)}_3\circ C_4$$ of the Dutch Windmill Graph and the cycle $$C_4$$ is not distance magic for any $$t>1$$ . [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order $${n\ge 3}$$ and size m and $${f:E(G)\to \mathbb{Z}_n}$$ an edge labeling of G. Define a vertex labeling $${f': V(G)\to \mathbb{Z}_n}$$ by $${f'(v)= \sum_{u\in N(v)}f(uv)}$$ where the sum is computed in $${\mathbb{Z}_n}$$ . If f′ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A graph G is modular edge-graceful if G contains a modular edge-graceful spanning tree. Several classes of modular edge-graceful trees are determined. For a tree T of order n where $${n\not\equiv 2 \pmod 4}$$ , it is shown that if T contains at most two even vertices or the set of even vertices of T induces a path, then T is modular edge-graceful. It is also shown that every tree of order n where $${n\not\equiv 2\pmod 4}$$ having diameter at most 5 is modular edge-graceful. [ABSTRACT FROM AUTHOR]