𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graphs satisfying a local ore-type condition

✍ Scribed by Asratian, A. S.; Broersma, H. J.; Van den Heuvel, J.; Veldman, H. J.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
497 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

For an integer i, a graph is called an L,-graph if, for each triple of vertices u, u , w with

and Khachatrian proved that connected Lo-graphs of order a t least 3 are hamiltonian, thus improving Ore's Theorem. All K1,3-free graphs are L1-graphs, whence recognizing hamiltonian L1-graphs is an NP-complete problem. The following results about L1graphs, unifying known results of Ore-type andknown results on Kl,3-free graphs, are obtained. Set X = {GIKp,p+l C G C Kp v Kp+l for some p 2 2) ( V denotes join).

If G is a 2-connected L1-graph, then G is I-tough unless G E 5%. Furthermore, if G is a connected L1-graph of order at least 3 such that IN(u) f-N(u)l L 2 for every pair of vertices u, u with d(u, U ) = 2, then G is hamiltonian unless G E X , and every pair of vertices x, y with d(x, y) L 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L1-graph of even order, then G has a perfect matching.

📜 SIMILAR VOLUMES

A characterization of panconnected graph
A characterization of panconnected graphs satisfying a local ore-type condition
✍ Asratian, A. S.; H�ggkvist, R.; Sarkisian, G. V. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

It is well known that a graph G of orderp 2 3 is Hamilton-connected if d(u) +d(v) 2 p + 1 for each pair of nonadjacent vertices u and w. In this paper we consider connected graphs G of order at least 3 for which where N ( z ) denote the neighborhood of a vertex z. We prove that a graph G satisfying

New Ore-Type Conditions for H-Linked Gra
New Ore-Type Conditions for H-Linked Graphs
✍ Michael Ferrara; Ronald Gould; Michael Jacobson; Florian Pfender; Jeffrey Powell 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

## Abstract For a fixed (multi)graph __H__, a graph __G__ is __H‐linked__ if any injection __f__: __V__(__H__)→__V__(__G__) can be extended to an __H__‐subdivision in __G__. The notion of an __H__ ‐linked graph encompasses several familiar graph classes, including __k__‐linked, __k__‐ordered and __

Ore-type degree conditions for a graph t
Ore-type degree conditions for a graph to be H-linked
✍ Alexandr V. Kostochka; Gexin Yu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB 👁 1 views

## Abstract Given a fixed multigraph __H__ with __V__(__H__) = {__h__~1~,…, __h__~m~}, we say that a graph __G__ is __H__‐linked if for every choice of __m__ vertices __v__~1~, …, ~v~~m~ in __G__, there exists a subdivision of __H__ in __G__ such that for every __i__, __v__~i~ is the branch vertex

How to generate local refinements of uns
How to generate local refinements of unstructured tetrahedral meshes satisfying a regularity ball condition
✍ Michal Křížek; Theofanis Strouboulis 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

A simple algorithm that generates local refinements of tetrahedral meshes is proposed. Refinements are made by tetrahedra, which are subdivided into eight, four, three, or two smaller tetrahedra. We prove that a regularity ball condition is satisfied for the refined mesh. This guarantees that tetrah

A sufficient condition for bipartite gra
A sufficient condition for bipartite graphs to be type one
✍ Xu, Baogang 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

The total chromatic number χ T (G) of graph G is the least number of colors assigned to V (G) ∪ E(G) such that no adjacent or incident elements receive the same color. In this article, we give a sufficient condition for a bipartite graph G to have χ T (G) = ∆(G) + 1.