Antimagic orientations of even regular graphs

A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to . A labeling of D is antimagic if no two vertices in D have the same vertex-sum, where the vertex-sum of a vertex for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz [On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232] initiated the study of antimagic labelings of digraphs, and conjectured that every connected graph admits an antimagic orientation, where an orientation D of a graph G is antimagic if D has an antimagic labeling. It remained unknown whether every disjoint union of cycles admits an antimagic orientation. In this article, we first answer this question in the positive by proving that every 2-regular graph has an antimagic orientation. We then show that for any integer , every connected, 2d-regular graph has an antimagic orientation. Our technique is new.     

Graphs of Large Linear Size Are Antimagic

Given a graph and a colouring , the induced colour of a vertex v is the sum of the colours at the edges incident with v. If all the induced colours of vertices of G are distinct, the colouring is called antimagic. If G has a bijective antimagic colouring , the graph G is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than K₂ are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least for some constant c; we improve on this result, proving the conjecture for graphs with average degree at least some constant d₀.     

Antimagic Labeling of Regular Graphs

A graph is antimagic if there is a one‐to‐one correspondence such that for any two vertices , . It is known that bipartite regular graphs are antimagic and nonbipartite regular graphs of odd degree at least three are antimagic. Whether all nonbipartite regular graphs of even degree are antimagic remained an open problem. In this article, we solve this problem and prove that all even degree regular graphs are antimagic.     

Feedback vertex set on AT-free graphs

We present a polynomial time algorithm to compute a minimum (weight) feedback vertex set for AT-free graphs, and extending this approach we obtain a polynomial time algorithm for graphs of bounded asteroidal number.     

OPTIMAL LABELLING OF UNIT INTERVAL GRAPHS

This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

Group distance magic and antimagic graphs

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups.     

Subgraphs in vertex neighborhoods of Kr‐free graphs

In a K_r‐free graph, the neighborhood of every vertex induces a K_{r ? 1}‐free subgraph. The K_r‐free graphs with the converse property that every induced K_{r ? 1}‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case r ? 3 due to Pach [ 8 ]. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004     

Minor‐order obstructions for the graphs of vertex cover 6

We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to k–VERTEX COVER graph families. In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of vertices for connected (disconnected) obstructions are shown to be sharp for all k > 0. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 163–178, 2002     

Antimagic labeling of generalized pyramid graphs

An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.     

Antimagic Properties of Graphs with Large Maximum Degree

An antimagic labeling of a graph with m edges and n vertices is a bijection from the set of edges to the integers such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In this article, we discuss antimagic properties of graphs that contain vertices of large degree. We also show that graphs with maximum degree at least are antimagic.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

(2,1)-Total labelling of outerplanar graphs

The (2,1)-total labelling number of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper we prove that if G is an outerplanar graph with maximum degree Δ(G), then if Δ(G)?5, or Δ(G)=3 and G is 2-connected, or Δ(G)=4 and G contains no intersecting triangles.     

Antimagic Labeling of Cubic Graphs

An antimagic labeling of a graph G is a one‐to‐one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.     

A new upper bound for the total vertex irregularity strength of graphs

We investigate the following modification of the well-known irregularity strength of graphs. Given a total weighting w of a graph G=(V,E) with elements of a set {1,2,…,s}, denote wt_G(v)=∑_evw(e)+w(v) for each vV. The smallest s for which exists such a weighting with wt_G(u)≠wt_G(v) whenever u and v are distinct vertices of G is called the total vertex irregularity strength of this graph, and is denoted by . We prove that for each graph of order n and with minimum degree δ>0.     

Distant total irregularity strength of graphs via random vertex ordering

Let $c:V\cup E\to \{1,2,\dots ,k\}$ be a (not necessarily proper) total colouring of a graph $G=(V,E)$ with maximum degree $\Delta$. Two vertices $u,v\in V$ are sum distinguished if they differ with respect to sums of their incident colours, i.e. $c\left(u\right)+{\sum }_{e?u}c\left(e\right)\ne c\left(v\right)+{\sum }_{e?v}c\left(e\right)$. The least integer $k$ admitting such colouring $c$ under which every $u,v\in V$ at distance $1\le d(u,v)\le r$ in $G$ are sum distinguished is denoted by ${\mathrm{ts}}_r\left(G\right)$. Such graph invariants link the concept of the total vertex irregularity strength of graphs with so-called 1-2-Conjecture, whose concern is the case of $r=1$. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that ${\mathrm{ts}}_r\left(G\right)\le (2+o\left(1\right)){\Delta }^{r?1}$ for every integer $r\ge 2$ and each graph $G$, thus improving the previously best result: ${\mathrm{ts}}_r\left(G\right)\le 3{\Delta }^{r?1}$.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.