Search

Let $G = (V, E)$ be a finite simple undirected graph without $K_2$ components. A bijection $f : E \rightarrow \{1, 2,\cdots, |E|\}$ is called a local antimagic labeling if for any two adjacent vertices $u$ and $v$, they have different vertex sums, i.e., $w(u) \neq w(v)$, where the vertex sum $w(u) = \sum_{e \in E(u)} f(e)$, and $E(u)$ is the set of edges incident to $u$. Thus any local antimagic labeling induces a proper vertex coloring of $G$ where the vertex $v$ is assigned the color (vertex sum) $w(v)$. The local antimagic chromatic number $\chi_{la}(G)$ is the minimum number of colors taken over all colorings induced by local antimagic labelings of $G$. It was conjectured \cite{Aru-Wang} that for every tree $T$ the local antimagic chromatic number $l+ 1 \leq \chi_{la} ( T )\leq l+2$, where $l$ is the number of leaves of $T$. In this article we verify the above conjecture for complete full $t$-ary trees, for $t \geq 2$. A complete full $t$-ary tree is a rooted tree in which all nodes have exactly $t$ children except leaves and every leaf is of the same depth. In particular we obtain that the exact value for the local antimagic chromatic number of all complete full $t$-ary trees is $ l+1$ for odd $t$., Comment: 15 pages, 6 figures

Let G = (V, E) be a connected graph with |V|= n and |E|= m. A bijection f : E → {1, 2, … , m} is called a local antimagic lableing if for any two adjacent vertices u and v, w(u) ≠ w(v), where w(u)=...

An edge-graceful labeling of a finite simple graph with p vertices and q edges is a bijection from the set of edges to the set of integers { 1 , 2 , ⋯ , q } such that the vertex sums are pairwise distinct modulo p, where the vertex sum at a vertex is the sum of labels of all edges incident to such vertex. A graph is called edge-graceful if it admits an edge-graceful labeling. In this article, we verify that an regular graph of odd degree is edge-graceful if it contains either of two particular 3-regular spanning subgraphs, namely, a quasi-prism factor and a claw factor.

Let G = ( V , E ) be a finite simple graph with p vertices and q edges, without isolated vertices or isolated edges. A vertex magic total labeling is a bijection f from V ∪ E to the consecutive integers 1 , 2 , ⋯ , p + q , with the property that, for every vertex u ∈ V , one has f ( u ) + ∑ u v ∈ E f ( u v ) = k for some constant k. The vertex magic total labeling is called E-super if f ( E ) = { 1 , 2 , ⋯ , q } . In this paper we verify the existence of E-super vertex magic total labeling for odd regular graphs containing a particular 3-factor.

A graceful labeling of a graph with q edges is a labeling of its vertices using the integers in [0, q], such that no two vertices are assigned the same label and each edge is uniquely identified by the absolute difference between the labels of its endpoints. The well known Graceful Tree Conjecture (GTC) states that all trees are graceful, and it remains open. It was proved in 1999 by Broersma and Hoede that there is an equivalent conjecture for GTC stating that all trees containing a perfect matching are strongly graceful (graceful with an extra condition). In this paper we extend the above result by showing that there exist infinitely many equivalent versions of the GTC. Moreover we verify these infinitely many equivalent conjectures of GTC for trees of diameter at most 7. Among others we are also able to identify new graceful trees and in particular generalize the ?-construction of Stanton-Zarnke (and later Koh- Rogers-Tan) for building graceful trees through two smaller given graceful trees.

Let G = ( V ( G ) , E ( G ) ) be a finite simple graph with p = | V ( G ) | vertices and q = | E ( G ) | edges, without isolated vertices or isolated edges. A vertex magic total labeling is a bijection from V ( G ) ∪ E ( G ) to the consecutive integers 1 , 2 , … , p + q , with the property that, for every vertex u in V ( G ) , one has f ( u ) + ∑ u v ∈ E ( G ) f ( u v ) = k for some constant k . Such a labeling is called E -super vertex magic if f ( E ( G ) ) = { 1 , 2 , … , q } . A graph G is called E -super vertex magic if it admits an E -super vertex magic labeling. More recently Marimuthu and Balakrishnan (2012) studied some basic properties of such labeling and established E -super vertex magic labeling of some families of graphs. In this note we extend their results and more examples are also provided.

Although the Cartesian product of two Hamiltonian graphs is Hamiltonian, the corresponding statement for directed graphs is not true. Indeed, it is known that it does not always hold even for the Cartesian products of two directed cycles. In this paper, we study the Cartesian product and its generalization of a directed graph G and a directed cycle. We show that if G has “strong” fault-Hamiltonicity properties, then so does G □ Cn, that is, the Cartesian product of G and a cycle of length n. We also discuss some related problems.

For a simple path P"r on r vertices, the square of P"r is the graph P"r^2 on the same set of vertices of P"r, and where every pair of vertices of distance two or less in P"r is connected by an edge. Given a (p,q)-graph G with p vertices and q edges, and a nonnegative integer k, G is said to be k-edge-graceful if the edges can be labeled bijectively by k,k+1,...,k+q-1, so that the induced vertex sums (modp) are pairwise distinct, where the vertex sum (modp) at a vertex is the sum of the labels of all edges incident to such a vertex, modulo the number of vertices p. We call the set of all such k the edge-graceful spectrum of G, and denote it by egI(G). In this article, the edge-graceful spectrum egI(P"r^2) for the square of paths P"r^2 is completely determined for odd r.

An(a,s)-vertex-antimagic edge labeling(or an(a,s)-VAElabeling, for short) ofGis a bijective mapping from the edge setE(G)of a graphGto the set of integers1,2,…,|E(G)|with the property that the vertex-weights form an arithmetic sequence starting fromaand having common differences, whereaandsare two positive integers, and the vertex-weight is the sum of the labels of all edges incident to the vertex. A graph is called(a,s)-antimagic if it admits an(a,s)-VAElabeling. In this paper, we investigate the existence of(a,1)-VAE labeling for disconnected 3-regular graphs. Also, we define and study a new concept(a,s)-vertex-antimagic edge deficiency, as an extension of(a,s)-VAE labeling, for measuring how close a graph is away from being an(a,s)-antimagic graph. Furthermore, the(a,1)-VAE deficiency of Hamiltonian regular graphs of even degree is completely determined. More open problems are mentioned in the concluding remarks.

In 1977, Alter and Wang (Uniquely intersectable graphs, Discrete Math. 18 (1977) 217{226) introduced the concept of unique intersectability of a graph. They showed that triangle-free is a sucient condition for a graph to be uniquely intersectable. In 1990, Tsuchiya (On intersection graphs with respect to antichains (II), Utilities Math. 37 (1996) 29{44) studied the concept of unique intersectability with respect to antichains and showed that triangle-free is also a sucient condition for a graph to be uniquely intersectable with respect to antichains. In this paper we generalize the above results by proving that if a graph is diamond-free and twins-free, then it is uniquely intersectable and if a graph is diamond-free and nonpendant brothers-free, then it is uniquely intersectable with respect to antichains. Also we characterize diamond-free graphs that are uniquely intersectable and the line graphs of triangle-free graphs that are uniquely intersectable. We also consider the concept of unique intersectability with respect to multifamilies and obtain a characterization of such graphs. c 1999 Elsevier Science B.V. All rights reserved.

A function f : V → { − 1 , 0 , 1 } is a minus-domination function of a graph G = ( V , E ) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f ( x ) over all vertices x ∈ V . In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for d -degenerate graphs when parameterized by the size of the minus-dominating set and by d , where the size of a minus domination is the number of vertices that are assigned 1 , (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is N P -complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination.

As an analogous concept of nowhere-zero flows for directed and bi-directed graphs, we consider zero-sum flows for undirected graphs in this article. For an undirected graph G, a zero-sum k -flow is an assignment of non-zero integers whose absolute values less than k to the edges, such that the sum of the values of all edges incident with each vertex is zero. Furthermore we generalize the notion via considering a combinatorial optimization problem, which is to calculate the zero-sum minimum flow number of a graph G, namely, the least integer k for which G may admit a zero-sum k-flow. The Zero-Sum 6-Flow Conjecture was raised by Akbari et al. in 2009: If a graph with a zero-sum flow, it admits a zero-sum 6-flow. It turns out that this conjecture was proved to be equivalent to the classical Bouchet 6-flow conjecture for bi-directed flows. In this paper, we study zero-sum minimum flow numbers of graphs induced from plane tiling by regular hexagons in an arbitrary way, namely, the hexagonal grid graphs. In particular we are able to verify the Zero-Sum 6-Flow Conjecture for the class of hexagonal grid graphs by determining the zero-sum flow number of any non-trivial hexagonal grid graph is 3 or 4. We further use the concept of dual graphs to specify classes of infinite families of hexagonal grid graphs with minimum flow numbers 3 and 4 respectively. Further open problems are included.

A function f: V → { − 1,0,1} is a minus-domination function of a graph G = (V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x ∈ V. In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for d-degenerate graphs when parameterized by the size of the minus-dominating set and by d, where the size of a minus domination is the number of vertices that are assigned 1, (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is NP-complete for splitgraphs, and (4) unless P = NP there is no fixed-parameter algorithm for minus-domination.

It is known that edge-magic-ness can be applied to the arrangement of devices of a wireless network, which is a special case of a general concept of arithmetic edge-antimagicness. A graph G with p vertices and q edges is called (a, d)-edge-antimagic if there exists an injective vertex labeling function ƒ: V(G) → {1, 2, ⋯, p} such that the induced edge labels, which are defined by ƒ(uv) = ƒ(u) + ƒ(v) for each uv ∈ E(G), form an arithmetic progression {a, a + d, a + 2d, ⋯⋯, a + (q − 1)d} where d is a positive integer. The (a, d)-edge-antimagic deficiency μ d (G) of a graph G, which is the least integer k such that G is (a, d)-edge-antimagic by modifying the range of the injective vertex labeling function from {1, 2, ⋯, p} to {1, 2, ⋯, p + k}. In this article, we completely determine the (a, d)-edge-antimagic deficiency of complete bipartite graphs K m,n , which in particular confirms a conjecture raised by R. Figueroa-Centeno et al. when d = 1.

An $L(2,1)$-labelling of a graph $G$ is an assignment of non-negative integers to the vertices of $G$ such that vertices at distance at most two get different numbers and adjacent vertices get numbers which are at least two apart. The $L(2,1)$-labelling number of $G$, denoted by $\lambda(G)$, is the minimum range of labels over all such labellings. In this paper, we first discuss some necessary and sufficient conditions for unit interval graph $G$ to have $\lambda(G)=2\chi(G)-2$ and then characterize all unit interval graphs $G$ of order no more than $3\chi(G)-1$, where $\chi(G)$ is the chromatic number of $G$. Finally, we discuss some subgraphs of unit interval graphs $G$ on more than $2\chi(G)+1$ vertices with $\lambda(G) = 2\chi(G)$.

For a graph G with vertices v"1,v"2,...,v"n, a simple set representation of G is a family F={S"1,S"2,...,S"n} of distinct nonempty sets such that |S"[email protected]?S"j|=1 if v"iv"j is an edge in G, and |S"[email protected]?S"j|=0 otherwise. Let S(F)[email protected]?"i"="1^nS"i, and let @w"s(G) denote the minimum |S(F)| of a simple set representation F of G. If, for every two minimum simple set representations F and F^' of G, F can be obtained from F^' by a bijective mapping from S(F^') to S(F), then G is said to be s-uniquely intersectable. In this paper, we are concerned with the s-unique intersectability of diamond-free graphs, where a diamond is a K"4 with one edge deleted. Moreover, for a diamond-free graph G, we also derive a formula for computing @w"s(G).