Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. KostochkaDouglas B. West — 2006

Discussiones Mathematicae Graph Theory

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that d i > i or d n - i n - i . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

Daniel W. CranstonSogol JahanbekamDouglas B. West — 2014

Discussiones Mathematicae Graph Theory

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...

The leafage of a chordal graph

In-Jen LinTerry A. McKeeDouglas B. West — 1998

Discussiones Mathematicae Graph Theory

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal...

Page 1

Download Results (CSV)