✦ LIBER ✦

Subgraphs of graphs, I

✍ Scribed by Paul A. Catlin

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 737 KB
Volume: 10
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(74)90119-8

No coin nor oath required. For personal study only.

✦ Synopsis

&et G' and H aphs on p vertices. We give a suffictent Londition, based f the verrices of G and the maximum degree of t w vertices of ff' for Throughout this paper, all graphs considered are finite and simpl;. The C&~WP of a vertex v in the graph G is denoted deg<; (v). The vertex set of G is dencted V(G). e say that a graph H can be embedded into h G if there is an injec V(H) -+ V(G) such that if v and acent in H, then w v) and R(W) are adjaceA in 9;. Given graphs WC give a sufficient condition for the existence of an emb e notation G(1, X) s r a bipartite graph wit!-1

📜 SIMILAR VOLUMES

Pancyclic subgraphs of random graphs

✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Characterizing subgraphs of Hamming grap

Characterizing subgraphs of Hamming graphs

✍ Sandi Klavžar; Iztok Peterin 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph __G__ is an induced subgraph of a Hamming graph i

Biregular subgraphs of biregular graphs

✍ S Sridharan 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 103 KB

Extremal subgraphs of random graphs

✍ László Babai; Miklós Simonovits; Joel Spencer 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 1015 KB

## Abstract We shall prove that if __L__ is a 3‐chromatic (so called “forbidden”) graph, and —__R__^__n__^ is a random graph on __n__ vertices, whose edges are chosen independently, with probability __p__, and —__B__^__n__^ is a bipartite subgraph of __R__^__n__^ of maximum size, —__F__^__n__^ is a

Graphs isomorphic to subgraphs of their

Graphs isomorphic to subgraphs of their line-graphs

✍ Douglas Bauer; Ralph Tindell 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 621 KB

## An emhdding of graph G into graph N is by definition an isomorphism OI G onto a subgraph of H. It is shown in this paper that every unicycle V embeds in its line-graph L(V), and that every other connected graph that embeds in its own line-graph may be constructed from such an embedded unicycle

Subgraph-avoiding coloring of graphs

✍ Jia Shen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract Given a “forbidden graph” __F__ and an integer __k__, an __F‐avoiding k‐coloring__ of a graph __G__ is a __k__‐coloring of the vertices of __G__ such that no maximal __F__‐free subgraph of __G__ is monochromatic. The __F‐avoiding chromatic number__ __ac__~__F__~(__G__) is the smallest i