Displaying similar documents to “A proof of the bounded graph conjecture.”

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.

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...

On Vizing's conjecture

Bostjan Bresar (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

α-Labelings of a Class of Generalized Petersen Graphs

Anna Benini, Anita Pasotti (2015)

Discussiones Mathematicae Graph Theory

Similarity:

An α-labeling of a bipartite graph Γ of size e is an injective function f : V (Γ) → {0, 1, 2, . . . , e} such that {|ƒ(x) − ƒ(y)| : [x, y] ∈ E(Γ)} = {1, 2, . . . , e} and with the property that its maximum value on one of the two bipartite sets does not reach its minimum on the other one. We prove that the generalized Petersen graph PSn,3 admits an α-labeling for any integer n ≥ 1 confirming that the conjecture posed by Vietri in [10] is true. In such a way we obtain an infinite class...

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.

Universality for and in Induced-Hereditary Graph Properties

Izak Broere, Johannes Heidema (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary...

Characterizing Cartesian fixers and multipliers

Stephen Benecke, Christina M. Mynhardt (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G ☐ H denote the Cartesian product of the graphs G and H. In 2004, Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G ☐ K₂) = γ(G), and noted that γ(G ☐ Kₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(G)+n-2 for each n such that 2 ≤ n < |V(G)|- γ(G)+2, and characterize this class of graphs. Also...

Radio Graceful Hamming Graphs

Amanda Niedzialomski (2016)

Discussiones Mathematicae Graph Theory

Similarity:

For k ∈ ℤ+ and G a simple, connected graph, a k-radio labeling f : V (G) → ℤ+ of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio labelings of G when k = diam(G). In this setting, f is injective; if f is also surjective onto {1, 2, . . . , |V (G)|}, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio...

Hereditarnia

Izak Broere, Peter Mihók (2013)

Discussiones Mathematicae Graph Theory

Similarity: