A note on pm-compact bipartite graphs

• Autorzy: Jinfeng Liu , Xiumei Wang
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

perfect matching; PM-compact graph; matching-covered graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 2
• Strony: 409-413

Daty

wydano

2014-05-01

online

2014-04-12

Twórcy

autor

Jinfeng Liu

• Center for Combinatorics and LPMC-TJKLC Nankai University, Tianjin 300071, China

autor

Xiumei Wang

• Department of Mathematics, Zhengzhou University Zhengzhou 450001, China

Bibliografia

• [1] C.A. Barefoot, R.C. Entringer and L.A. Sz´ekely, Extremal values for ratios of dis- tances in trees, Discrete Appl. Math. 80 (1997) 37-56. doi:10.1016/S0166-218X(97)00068-1[Crossref]
• [2] A.A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math 66 (2001) 211-249. doi:10.1023/A:1010767517079[Crossref]
• [3] L. Johns and T.C. Lee, S-distance in trees, in: Computing in the 90’s (Kalamazoo, MI, 1989), Lecture Notes in Comput. Sci., 507, N.A. Sherwani, E. de Doncker and J.A. Kapenga (Ed(s)), (Springer, Berlin, 1991) 29-33. doi:10.1007/BFb0038469[Crossref]
• [4] T. Lengyel, Some graph problems and the realizability of metrics by graphs, Congr. Numer. 78 (1990) 245-254

Identyfikatory

DOI

10.7151/dmgt.1706