Perfect Matchings in a Class of Bipartite Graphs
Ivan Gutman (1989)
Publications de l'Institut Mathématique
Similarity:
Ivan Gutman (1989)
Publications de l'Institut Mathématique
Similarity:
Tomislav Doslić (2005)
Discussiones Mathematicae Graph Theory
Similarity:
It is shown in this note that some matching-related properties of graphs, such as their factor-criticality, regularizability and the existence of perfect 2-matchings, are preserved when iterating Mycielski's construction.
A. Gyárfás (1987)
Applicationes Mathematicae
Similarity:
Arie M. C. A. Koster, Annegret K. Wagler (2008)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope coincides with the fractional stable set polytope . For all imperfect graphs it holds that . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss...
Andrzej Włoch (1999)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
Eugen Mândrescu (1991)
Czechoslovak Mathematical Journal
Similarity:
Ivan Gutman (1991)
Publications de l'Institut Mathématique
Similarity:
P. John, H. Sachs, H. Zernitz (1987)
Applicationes Mathematicae
Similarity:
Van Bang Le (2000)
Discussiones Mathematicae Graph Theory
Similarity:
Magda Dettlaff, Magdalena Lemańska, Gabriel Semanišin, Rita Zuazua (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure...
Jinfeng Liu, Xiumei Wang (2014)
Discussiones Mathematicae Graph Theory
Similarity:
A graph is called perfect matching compact (briefly, PM-compact), if its perfect matching graph is complete. Matching-covered PM-compact bipartite graphs have been characterized. In this paper, we show that any PM-compact bipartite graph G with δ (G) ≥ 2 has an ear decomposition such that each graph in the decomposition sequence is also PM-compact, which implies that G is matching-covered
G. L. Garg, B. Kumar (1989)
Matematički Vesnik
Similarity: