✦ LIBER ✦

On smallest regular graphs with a given isopart

✍ Scribed by John Frederick Fink

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 408 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090108

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphs H having a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a connected regular graph H having a decomposition into t subgraphs isomorphic to G. In this article, the values of these parameters are determined for complete graphs, cycles, and stars. Furthermore, we show that Δ(T) ⩽ r(T) ⩽ δ (T) + 1 for every tree T. and r(T) Δ(T) if the maximum degree Δ(T) is even.

📜 SIMILAR VOLUMES

Smallest regular graphs with prescribed

Smallest regular graphs with prescribed odd girth

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

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__

Regular graphs with given girth pair

✍ Frank Harary; Peter Kovács 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 453 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 is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is

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

On graphs with a given endomorphism mono

On graphs with a given endomorphism monoid

✍ Václav Koubek; Vojtěch Rödl; Benjamin Shemmer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB 👁 1 views

## Abstract Hedrlín and Pultr proved that for any monoid **M** there exists a graph __G__ with endomorphism monoid isomorphic to **M**. In this paper we give a construction __G__(__M__) for a graph with prescribed endomorphism monoid **M**. Using this construction we derive bounds on the minimum nu

On graphs containing a given graph as ce

On graphs containing a given graph as center

✍ Fred Buckley; Zevi Miller; Peter J. Slater 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB 👁 1 views

## Abstract We examine the problem of embedding a graph __H__ as the center of a supergraph __G__, and we consider what properties one can restrict __G__ to have. Letting __A(H)__ denote the smallest difference ∣__V(G)__∣ ‐ ∣__V(H)__∣ over graphs __G__ having center isomorphic to __H__ it is demons

A note on regular Ramsey graphs

✍ Noga Alon; Sonny Ben-Shimon; Michael Krivelevich 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB

## Abstract We prove that there is an absolute constant __C__>0 so that for every natural __n__ there exists a triangle‐free __regular__ graph with no independent set of size at least \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle