✦ LIBER ✦

Every connected, locally connected graph is upper embeddable

✍ Scribed by Ladislav Nebeský

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 154 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050211

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this Note it is proved that every connected, locally connected graph is upper embeddable. Moreover, a lower bound for the maximum genus of the square of a connected graph is given.

📜 SIMILAR VOLUMES

Every 3-connected, locally connected, cl

Every 3-connected, locally connected, claw-free graph is Hamilton-connected

✍ Asratian, A. S. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 639 KB

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of orderp 2 4, containing no induced subgraph isomorphic to K1,31 is Hamilton-connected if and only if G is 3connected.

Every connected, locally connected nontr

Every connected, locally connected nontrivial graph with no induced claw is hamiltonian

✍ David J. Oberly; Slobodan K. Simić; David P. Sumner 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on __p__ ≥ 3 vertices and having no induced __K__~1,3~ is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtain

Every connected graph is a query graph

✍ Peter M. Winkler 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

Let Vbe a set of bit strings of length k, i.e., V C {0, l}'. The query graph Q ( V ) is defined as follows: the vertices of Q(V) are the elements of V, and {O,V} is an edge of Q ( V ) if and only if no other W E Vagrees with U in all the positions in which V does. If Vrepresents the set of keys for

Every 3-connected claw-free Z8-free grap

Every 3-connected claw-free Z8-free graph is Hamiltonian

✍ Hong-Jian Lai; Liming Xiong; Huiya Yan; Jin Yan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

## Abstract In this article, we first show that every 3‐edge‐connected graph with circumference at most 8 is supereulerian, which is then applied to show that a 3‐connected claw‐free graph without __Z__~8~ as an induced subgraph is Hamiltonian, where __Z__~8~ denotes the graph derived from identify

Local connectivity of a random graph

✍ P. Erdös; E. M. Palmer; R. W. Robinson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract A graph is locally connected if for each vertex ν of degree __≧2__, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order __n_

Connected, locally 2-connected, K1,3-fre

Connected, locally 2-connected, K1,3-free graphs are panconnected

✍ S. V. Kanetkar; P. R. Rao 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

## Abstract A graph __G__ is locally __n__‐connected, __n__ ≥ 1, if the subgraph induced by the neighborhood of each vertex is __n__‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to __K__~1,3~ is panconnected.