Premium
Det‐extremal cubic bipartite graphs
Author(s) -
Funk M.,
Jackson Bill,
Labbate D.,
Sheehan J.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10131
Subject(s) - bipartite graph , combinatorics , adjacency matrix , mathematics , foster graph , complete bipartite graph , cubic graph , edge transitive graph , extremal graph theory , pancyclic graph , discrete mathematics , graph , line graph , 1 planar graph , voltage graph
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