✦ LIBER ✦

A Criterion for the t-Vertex Condition of Graphs

✍ Scribed by Sven Reichard

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 126 KB
Volume: 90
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.3045

No coin nor oath required. For personal study only.

✦ Synopsis

Combining two concepts of regularity of graphs, namely k-isoregularity and the t-vertex condition, a generalization of a classical result by Hestenes and Higman is presented. As an application it is shown that two infinite series of graphs constructed by Brouwer, Ivanov, and Klin which are not rank 3 satisfy the 5-vertex condition.

📜 SIMILAR VOLUMES

A criterion for the planarity of a graph

✍ Jerome R. Breitenbach 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 1 views

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244-2711 has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion whi

A degree condition for the circumference

A degree condition for the circumference of a graph

✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper

On the linear vertex-arboricity of a pla

On the linear vertex-arboricity of a planar graph

✍ K. S. Poh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

## Abstract We prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and others.

Minor-order obstructions for the graphs

Minor-order obstructions for the graphs of vertex cover 6

✍ Michael J. Dinneen; Liu Xiong 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB 👁 1 views

## Abstract We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to __k__–VERTEX C

A necessary and sufficient condition for

A necessary and sufficient condition for the star decomposition of complete graphs

✍ Lin, Chiang; Shyu, Tay-Woei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

In this paper w e prove the following result. Let ml 2 m2 2 ... 2 ml be nonnegative integers. A necessary and sufficient condition for the complete graph K,, to be decomposed into stars S,,, , S

Some new bounds for the maximum number o

Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

✍ Byer, Owen D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 3 views

Let f (v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f (v, e, λ). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve