Displaying similar documents to “Complete minors, independent sets, and chordal graphs”

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.

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.

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.

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

The chromaticity of a family of 2-connected 3-chromatic graphs with five triangles and cyclomatic number six

Halina Bielak (1998)

Discussiones Mathematicae Graph Theory

Similarity:

In this note, all chromatic equivalence classes for 2-connected 3-chromatic graphs with five triangles and cyclomatic number six are described. New families of chromatically unique graphs of order n are presented for each n ≥ 8. This is a generalization of a result stated in [5]. Moreover, a proof for the conjecture posed in [5] is given.

The flower conjecture in special classes of graphs

Zdeněk Ryjáček, Ingo Schiermeyer (1995)

Discussiones Mathematicae Graph Theory

Similarity:

We say that a spanning eulerian subgraph F ⊂ G is a flower in a graph G if there is a vertex u ∈ V(G) (called the center of F) such that all vertices of G except u are of the degree exactly 2 in F. A graph G has the flower property if every vertex of G is a center of a flower. Kaneko conjectured that G has the flower property if and only if G is hamiltonian. In the present paper we prove this conjecture in several special classes of graphs, among others in squares...

Relating 2-Rainbow Domination To Roman Domination

José D. Alvarado, Simone Dantas, Dieter Rautenbach (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize...

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

Placing bipartite graphs of small size II

Beata Orchel (1996)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.

Isomorphic components of Kronecker product of bipartite graphs

Pranava K. Jha, Sandi Klavžar, Blaž Zmazek (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.