On Unicyclic Graphs with Uniquely Restricted Maximum Matchings

Vadim E. Levit, Eugen Mandrescu

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

1 ציטוט ‏(Scopus)

תקציר

A graph is called unicyclic if it owns only one cycle. A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. Clearly, μr(G) ≤ μ(G), where μr(G) denotes the size of a maximum uniquely restricted matching, while μ(G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μr(G) = μ(G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings.

שפה מקוריתאנגלית
עמודים (מ-עד)1867-1879
מספר עמודים13
כתב עתGraphs and Combinatorics
כרך29
מספר גיליון6
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - נוב׳ 2013

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On Unicyclic Graphs with Uniquely Restricted Maximum Matchings'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי