✦ LIBER ✦

Up-embeddability of graphs with small order

✍ Scribed by Shengxiang Lv; Yanpei Liu

Publisher: Elsevier Science
Year: 2010
Tongue: English
Weight: 528 KB
Volume: 23
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.10.001

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a 2-edge connected simple graph with girth g and minimal degree δ ≥ 3. If one of the following conditions is satisfied:

Here, M(δ, g) is the Moore bound of the (δ, g)-cage. As a corollary, there exists a constant c such that when δ > r |V (G)|-6 c + 1 (r = g-1 2), G is up-embeddable.

📜 SIMILAR VOLUMES

Graphs with constant link and small degr

Graphs with constant link and small degree or order

✍ J. I. Hall 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 957 KB

The graph G has constant link L if for each vertex x of. G the graph induced by G on the, vertices adjacent to x is isomorphic to L. For each graph L on 6 or fewer vertices w e decide whether or not there exists a graph G with constant link L. From this w e are able to list all graphs on 11 or fewer

Decomposing large graphs with small grap

Decomposing large graphs with small graphs of high density

✍ Yuster, Raphael 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 2 views

It is shown that for every positive integer h, and for every > 0, there are graphs H = (V H , E H ) with at least h vertices and with density at least 0.5with the following property: any graph with minimum degree at least |V G | 2 (1 + o(1)) and |E H | divides |E G |, then G has an H-decomposition.

Graphs with small numbers of independent

Graphs with small numbers of independent edges

✍ Miroslav M. Petrović; Ivan Gutman; Mirko Lepović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 327 KB

The graphs with exactly one, two or three independent edges are determined.

Graphs with special neighbourhood orderi

Graphs with special neighbourhood orderings of vertices

✍ Halina Bielak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 356 KB

Extremal graphs with bounded densities o

Extremal graphs with bounded densities of small subgraphs

✍ Griggs, Jerrold R.; Simonovits, Mikl�os; Thomas, George Rubin 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 1 views

Let Ex(n, k, µ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most µ edges. Here we summarize some known results of the problem of determining Ex(n, k, µ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

Nonexistence of certain cubic graphs wit

Nonexistence of certain cubic graphs with small diameters

✍ Leif K. Jørgensen 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 560 KB

We consider the maximum number of vertices in a cubic graph with small diameter. We show that a cubic graph of diameter 4 has at most 40 vertices. (The Moore bound is 46 and graphs with 38 vertices are known.) We also consider bipartite cubic graphs of diameter 5, for which the Moore bound is 62. We