Contents

On the Existence of Almost-Regular-Graphs with Exactly One 1-Factor

L. Caccetta 1, S. Mardiyono 1
1School of Mathematics and Statistics Curtin University of Technology GPO Box U1987 Perth, 6001 Western Australia

Abstract

A \(1\)-\emph{factor} of a graph \(G\) is a \(1\)-regular spanning subgraph of \(G\).
A graph \(G\) has exactly \(t\) \(1\)-factors if the maximum set of edge-disjoint
\(1\)-factors is \(t\). For given non-negative integers \(d\), \(t\), and even \(e\),
let \(\mathcal{G}(2n; d, e, t)\) be the class of simple connected graphs
on \(2n\) vertices, \((2n-1)\) of which have degree \(d\) and one has degree \(d+e\),
having exactly \(t\) \(1\)-factors. The problem that arises is that of determining
when \(\mathcal{G}(2n; d, e, t) \neq \emptyset ?\)
Recently, we resolved the case \(t = 0\). In this paper, we will consider the case \(t = 1\).