✦ LIBER ✦

The n-ordered graphs: A new graph class

✍ Scribed by Anthony Bonato; Jeannette Janssen; Changping Wang

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 147 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20352

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R^(n)^, which we name the infinite random n‐ordered graphs. The graphs R^(n)^ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R^(n)^ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R^(n)^ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R^(n)^. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009

📜 SIMILAR VOLUMES

A class of upper-embeddable graphs

✍ F. Jaeger; C. Payan; N. H. Xuong 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract In this paper, we prove the following result: Every graph obtained by connecting (with any number of edges) two vertex‐disjoint upper‐embeddable graphs graphs with even Betti number is upper‐embeddable.

A class of Hamiltonian regular graphs

✍ Paul Erdös; Arthur M. Hobbs 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 317 KB

## Abstract In this paper, we show that __n__ ⩾ 4 and if __G__ is a 2‐connected graph with 2__n__ or 2__n__−1 vertices which is regular of degree __n__−2, then __G__ is Hamiltonian if and only if __G__ is not the Petersen graph.

Constructing a Class of Symmetric Graphs

✍ Sanming Zhou 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

We find a natural construction of a large class of symmetric graphs from point-and block-transitive 1-designs. The graphs in this class can be characterized as G-symmetric graphs whose vertex sets admit a G-invariant partition B of block size at least 3 such that, for any two blocks B, C of B, eithe

Forbidden ordered subgraph vs. forbidden

Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes

✍ Ginn, Mark 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB

We show that the minimum set of unordered graphs that must be forbidden to get the same graph class characterized by forbidding a single ordered graph is infinite.

On the Complexity of Recognizing Hamming

On the Complexity of Recognizing Hamming Graphs and Related Classes of Graphs

✍ Wilfried Imrich; Sandi Klavzar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 287 KB

A note on graphs and sphere orders

✍ Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract A partially ordered set __P__ is called a __k‐sphere order__ if one can assign to each element a ∈ __P__ a ball __B__~__a__~ in __R^k^__ so that __a__ < __b__ iff __B__~__a__~ ⊂ __B__~__b__~. To a graph __G__ = (__V,E__) associate a poset __P__(__G__) whose elements are the vertices and