Displaying similar documents to “On Vizing's conjecture”

Vizing's conjecture and the one-half argument

Bert Hartnell, Douglas F. Rall (1995)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as...

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

A Survey of the Path Partition Conjecture

Marietjie Frick (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

On a special case of Hadwiger's conjecture

Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.

An Oriented Version of the 1-2-3 Conjecture

Olivier Baudon, Julien Bensmail, Éric Sopena (2015)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct...

Highly connected counterexamples to a conjecture on α-domination

Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.

On the p-domination number of cactus graphs

Mostafa Blidia, Mustapha Chellali, Lutz Volkmann (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.

Vertex-disjoint copies of K¯₄

Ken-ichi Kawarabayashi (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge. In this paper, we propose the following conjecture: Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ. This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.

Lower bounds for integral functionals generated by bipartite graphs

Barbara Kaskosz, Lubos Thoma (2019)

Czechoslovak Mathematical Journal

Similarity:

We study lower estimates for integral fuctionals for which the structure of the integrand is defined by a graph, in particular, by a bipartite graph. Functionals of such kind appear in statistical mechanics and quantum chemistry in the context of Mayer's transformation and Mayer's cluster integrals. Integral functionals generated by graphs play an important role in the theory of graph limits. Specific kind of functionals generated by bipartite graphs are at the center of the famous and...

A Note on Barnette’s Conjecture

Jochen Harant (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.