Premium
Induced Decompositions of Graphs
Author(s) -
Bondy J. Adrian,
Szwarcfiter Jayme L.
Publication year - 2013
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.21654
Subject(s) - combinatorics , mathematics , cograph , induced subgraph , pancyclic graph , discrete mathematics , split graph , graph , chordal graph , 1 planar graph , vertex (graph theory)
We consider those graphs G that admit decompositions into copies of a fixed graph F , each copy being an induced subgraph of G . We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.
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