Premium
Quartic Graphs with Every Edge in a Triangle
Author(s) -
Pfender Florian,
Royle Gordon F.
Publication year - 2016
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.21892
Subject(s) - multigraph , combinatorics , mathematics , quartic function , corollary , cubic graph , quartic graph , line graph , graph , discrete mathematics , voltage graph , pure mathematics
Abstract We characterize the quartic (i.e., 4‐regular) multigraphs with the property that every edge lies in a triangle. The main result is that such graphs are either squares of cycles, line multigraphs of cubic multigraphs, or are obtained from these by a number of simple subgraph‐replacement operations. A corollary of this is that a simple quartic graph with every edge in a triangle is either the square of a cycle, the line graph of a cubic graph or a graph obtained from the line multigraph of a cubic multigraph by replacing triangles with copies of K 1, 1, 3 .