Totally equimatchable graphs
type: Item
instance of: scholarly article
title: Totally equimatchable graphs
zbMATH Open document ID: 0873.05070
DOI: 10.1016/S0012-365X(96)00062-3
author: Jerzy Topp
author: Preben Dahl Vestergaard
published in: Discrete Mathematics
publication date: 1997-10-26T00:00:00Z
review text: Let \(G=(V,E)\) be a connected graph. The elements of the set \(V(G)\cup E(G)\) are called elements of \(G\). A set \(M\) of elements of \(G\) is called a total matching if the elements of \(M\) are pairwise independent, and \(G\) is totally equimatchable if every maximal total matching of \(G\) is maximum. The authors characterize totally equimatchable graphs. When complete graphs are denoted by \(K_n\), complete bipartite graphs by \(K_{n,n}\) and complete windmills by \(K_1+\bigcup^n_{i=1} K_{2m_i}\), where \(K_1+\bigcup^n_{i=1} K_{2m_i}\) is the graph obtained from the disjoint union of \(K_1\), \(K_{2m_1},\dots,K_{2m_n}\) by joining the only vertex of \(K_1\) to every vertex in \(\bigcup^n_{i=1} V(K_{2m_i})\), they prove as main result that a connected graph is totally equimatchable iff it is one of the graphs \(K_n\), \(K_{n,n}\), and \(K_1+\bigcup^n_{i=1} K_{2m_i}\), where \(n\) and \(m_1,\dots,m_n\) are any positive integers. Moreover, the precise values of certain parameters and their interrelations are given.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1019073
zbMATH Keywords: total matching
zbMATH Keywords: totally equimatchable graphs
zbMATH Keywords: complete graphs
zbMATH Keywords: bipartite graphs
zbMATH Keywords: windmills
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Total matchings and total coverings of graphs
cites work: Q3818315
cites work: Equimatchable factor‐critical graphs
cites work: Parallel concepts in graph theory
cites work: Matching theory
cites work: Some covering concepts in graphs
cites work: WELL-COVERED GRAPHS: A SURVEY
cites work: Randomly matchable graphs
description: scientific article; zbMATH DE number 1019073