Premium
The symmetric (2 k, k )‐graphs
Author(s) -
Kriesell Matthias
Publication year - 2001
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/1097-0118(200101)36:1<35::aid-jgt4>3.0.co;2-j
Subject(s) - combinatorics , mathematics , symmetric graph , vertex transitive graph , discrete mathematics , cograph , transitive relation , 1 planar graph , vertex (graph theory) , graph , line graph , voltage graph
A noncomplete graph G is called an ( n, k )‐graph if it is n ‐connected and G − X is not ( n − | X | + 1)‐connected for any X ⊆ V ( G ) with | X | ≤ k . Mader conjectured that for k ≥ 3 the graph K 2 k + 2 − (1‐ factor ) is the unique (2 k, k )‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001