Premium
Equimatchable Regular Graphs
Author(s) -
Akbari Saieed,
Ghodrati Amir Hossein,
Hosseinzadeh Mohammad Ali,
Iranmanesh Ali
Publication year - 2018
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.22138
Subject(s) - mathematics , combinatorics , strongly regular graph , symmetric graph , graph , vertex transitive graph , discrete mathematics , pancyclic graph , 1 planar graph , chordal graph , line graph , pathwidth , graph power , voltage graph
A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K 4 and K 3, 3 . We extend this result by showing that for an odd positive integer r , if G is a connected equimatchable r ‐regular graph, then G ∈ { K r + 1 , K r , r } . Also it is proved that for an even r , a connected triangle‐free equimatchable r ‐regular graph is isomorphic to one of the graphs C 5 , C 7 , and K r , r .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom