𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New Ore-Type Conditions for H-Linked Graphs

✍ Scribed by Michael Ferrara; Ronald Gould; Michael Jacobson; Florian Pfender; Jeffrey Powell; Thor Whalen

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
127 KB
Volume
71
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012

📜 SIMILAR VOLUMES

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

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

On graphs satisfying a local ore-type co
On graphs satisfying a local ore-type condition
✍ Asratian, A. S.; Broersma, H. J.; Van den Heuvel, J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 497 KB

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

An extremal problem for H-linked graphs
An extremal problem for H-linked graphs
✍ Alexandr Kostochka; Gexin Yu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract We introduce the notion of __H__‐linked graphs, where __H__ is a fixed multigraph with vertices __w__~1~,…,__w__~m~. A graph __G__ is __H__‐__linked__ if for every choice of vertices υ~1~,…, υ~m~ in __G__, there exists a subdivision of __H__ in __G__ such that υ~i~ is the branch vertex

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

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

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.