✦ LIBER ✦

Det-extremal cubic bipartite graphs

✍ Scribed by M. Funk; Bill Jackson; D. Labbate; J. Sheehan

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 132 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10131

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003

📜 SIMILAR VOLUMES

Extremal bipartite subgraphs of cubic tr

Extremal bipartite subgraphs of cubic triangle-free graphs

✍ Glenn Hopkins; William Staton 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB

## Abstract A cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

Edge proximity conditions for extendabil

Edge proximity conditions for extendability in cubic bipartite graphs

✍ R. E. L. Aldred; Bill Jackson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

## Abstract We show that a set __M__ of __m__ edges in a cyclically (3__m__ − 2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in __M__ are pairwise distance at least __f__(__m__) apart, where © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007

Extremal interval graphs

✍ Jürgen Eckhoff 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB

## Abstract An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for t

s-Regular cubic graphs as coverings of t

s-Regular cubic graphs as coverings of the complete bipartite graph K3,3

✍ Yan-Quan Feng; Jin Ho Kwak 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract A graph is __s‐regular__ if its automorphism group acts freely and transitively on the set of __s__‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the __s__‐regular cyclic cov

Koszul Bipartite Graphs

✍ Hidefumi Ohsugi; Takayuki Hibi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 48 KB