✦ LIBER ✦

Balanced graphs and noncovering graphs

✍ Scribed by Oliver Pretzel; Dale Youngs

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 532 KB
Volume: 88
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90015-t

No coin nor oath required. For personal study only.

✦ Synopsis

Pretzel, 0. and D. Youngs, Balanced graphs and noncovering graphs, Discrete Mathematics, 88 (1991) 279-287. Probabilistic arguments show that triangle-free noncovering graphs are very common. Nevertheless, few specific examples are known. In this paper we describe a simple method of constructing a large family of such graphs. We first construct graphs that have very restricted diagram orientations and then show that identifying certain sets of vertices in one of these graphs produces a noncovering graph.

📜 SIMILAR VOLUMES

Strongly balanced graphs and random grap

Strongly balanced graphs and random graphs

✍ Andrzej Ruciński; Andrew Vince 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 455 KB

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with u vertices and e edges if and only if I s u -1 s e s ( 2 " ) . This result is applied to a classic question of Erdos and Renyi: What is the probability that a random graph on n vertices

Domination-balanced graphs

✍ Charles Payan; Nguyen Huy Xuong 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract A set __D__ of vertices in a graph is said to be a dominating set if every vertex not in __D__ is adjacent to some vertex in __D.__ The domination number β(__G__) of a graph __G__ is the size of a smallest dominating set. __G__ is called domination balanced if its vertex set can be part

On balanced signed graphs and consistent

On balanced signed graphs and consistent marked graphs

✍ Fred S. Roberts 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 560 KB

Balanced graphs and network flows

✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB

A graph G is balanced if the maximum ratio of edges to vertices, taken over all subgraphs of G, occurs at G itself. This note uses the max-flow/min-cut theorem to prove a good characterization of balanced graphs. This characterization is then applied to some results on how balanced graphs may be com

Balanced coloring of bipartite graphs

✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

Balanced judicious bipartitions of graph

Balanced judicious bipartitions of graphs

✍ Baogang Xu; Juan Yan; Xingxing Yu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract A bipartition of the vertex set of a graph is called __balanced__ if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if __G__ is a graph with minimum degree of at least 2 then __V__(__G__)