Bensmail, Julien Inerney, Fionn Mc Lyngsie, Kasper Szabo
Published in
Discussiones Mathematicae Graph Theory

For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑e∈E(v) w(e) ≠ ∑e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a + 2}-edge-weightings where a ∈ ℤ is odd. We show that a ...

Dyer, Danny Howell, Jared
Published in
Discussiones Mathematicae Graph Theory

A watchman’s walk for a graph G is a minimum-length closed dominating walk, and the length of such a walk is denoted (G). We introduce several lower bounds for such walks, and apply them to determine the length of watchman’s walks in several grids.

Kemnitz, Arnfried Marangio, Massimiliano
Published in
Discussiones Mathematicae Graph Theory

For an arbitrary invariant ρ(G) of a graph G the ρ-edge stability number esρ(G) is the minimum number of edges of G whose removal results in a graph H ⊆ G with ρ(H) ≠ ρ(G) or with E(H) = ∅. In the first part of this paper we give some general lower and upper bounds for the ρ-edge stability number. In the second part we study the χ′-edge stability n...

Wang, Jieyan
Published in
Discussiones Mathematicae Graph Theory

An embedding of a graph H in a graph G is an injection (i.e., a one-to-one function) σ from the vertices of H to the vertices of G such that σ(x)σ(y) is an edge of G for all edges xy of H. The image of H in G under σ is denoted by σ(H). A k-packing of a graph H in a graph G is a sequence (σ1, σ2,…, σk) of embeddings of H in G such that σ1(H), σ2(H)...

Colucci, Lucas Győri, Ervin
Published in
Discussiones Mathematicae Graph Theory

We extend a result of Griggs and Yeh about the maximum possible value of the L(2, 1)-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented L(2, 1)-labeling number and in some variants we introduce.

Sittitrai, Pongpat Nakprasit, Kittikorn
Published in
Discussiones Mathematicae Graph Theory

A graph G is list vertex k-arborable if for every k-assignment L, one can choose f(v) ∈ L(v) for each vertex v so that vertices with the same color induce a forest. In [6], Borodin and Ivanova proved that every planar graph without 4-cycles adjacent to 3-cycles is list vertex 2-arborable. In fact, they proved a more general result in terms of varia...

Mohr, Elena Rautenbach, Dieter
Published in
Discussiones Mathematicae Graph Theory

We show that every claw-free cubic graph of order n at least 8 has at most 2⌊ n4 ⌋ {2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.

Wang, Jing Cai, Junliang Lv, Shengxiang Huang, Yuanqiu
Published in
Discussiones Mathematicae Graph Theory

Thomassen described all (except finitely many) regular tilings of the torus S1 and the Klein bottle N2 into (3,6)-tilings, (4,4)-tilings and (6,3)-tilings. Many researchers made great e orts to investigate the crossing number of the Cartesian product of an m-cycle and an n-cycle, which is a special kind of (4,4)-tilings, either in the plane or in t...

Lin, Jenq-Jong Jou, Min-Jen
Published in
Discussiones Mathematicae Graph Theory

Let F, G and H be graphs. A (G, H)-decomposition of F is a partition of the edge set of F into copies of G and copies of H with at least one copy of G and at least one copy of H. For R ⊆ F, a (G, H)-covering of F with padding R is a (G, H)-decomposition of F + E(R). A (G, H)-covering of F with the smallest cardinality is a minimum (G, H)-covering. ...

Durhuus, Bergfinnur Lucia, Angelo
Published in
Discussiones Mathematicae Graph Theory

We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitney’s broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the r-complete hypergraph in terms o...