✦ LIBER ✦

The structure of (t,r)-regular graphs of large order

✍ Scribed by Robert E. Jamison; Peter D. Johnson Jr.

Book ID: 104113296
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 97 KB
Volume: 272
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(03)00200-0

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is (t; r)-regular i it has at least one independent t-set of vertices and the open neighborhood of any such set contains exactly r vertices. Our goal is to show that when t ¿ 3 and the order is su ciently large, then the structure of (t; r)-regular graphs is similar to, but not exactly the same as the structure of (2; r)-regular graphs as derived by Faudree and Knisley. That is, there is an "almost" complete kernel of order at most r surrounded by satellite cliques, all of the same order, which are "mostly" joined to the kernel.

📜 SIMILAR VOLUMES

The expected eigenvalue distribution of

The expected eigenvalue distribution of a large regular graph

✍ Brendan D. McKay 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 642 KB

On the bipartite density of regular grap

On the bipartite density of regular graphs with large girth

✍ Ondřej Zýka 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 1 views

## Abstract Let __B(G)__ be the edge set of a bipartite subgraph of a graph __G__ with the maximum number of edges. Let __b~k~__ = inf{|__B(G)__|/|__E(G)__‖__G__ is a cubic graph with girth at least __k__}. We will prove that lim~k → ∞~ __b~k~__ ≥ 6/7.

The Structure of Random Graph Orders

✍ Bollobás, Béla; Brightwell, Graham 📂 Article 📅 1997 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 374 KB

The geometry of t-spreads in k-walk-regu

The geometry of t-spreads in k-walk-regular graphs

✍ C. Dalfó; M. A. Fiol; E. Garriga 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 1 views

## Abstract A graph is walk‐regular if the number of closed walks of length ℓ rooted at a given vertex is a constant through all the vertices for all ℓ. For a walk‐regular graph __G__ with __d__+1 different eigenvalues and spectrally maximum diameter __D__=__d__, we study the geometry of its __d__‐

A lower bound on the order of regular gr

A lower bound on the order of regular graphs with given girth pair

✍ C. Balbuena; T. Jiang; Y. Lin; X. Marcote; M. Miller 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, __g__)‐cage is a small

The maximum valency of regular graphs wi

The maximum valency of regular graphs with given order and odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc