Inequalities for Total Matchings of Graphs

John Gimbel 1, Preben D. Vestergaard 2
1Department of Mathematics University of Alaska Fairbanks, Alaska
2Department of Mathematics University of Aalborg Denmark

Abstract

As a generalization of a matching consisting of edges only, Alavi et al. in [1] define a total matching which may contain both edges and vertices. Using total matchings, [1] defines a parameter \(\beta’_2(G)\) and proves that \(\beta’_2(G) \leq p-1\) holds for a connected graph of order \(p \geq 2\).
Our main result is to improve this inequality to \(\beta’_2(G) \leq p-2\sqrt{p}+{2}\) and we give an example demonstrating this bound to be best possible.
Relations of several other parameters to \(\beta’_2\) are demonstrated.