Equivalence classes in matching covered graphs

Autor(es)

Lu, Fuliang ^[1] ; Kothari, Nishad ^[2] ; Feng, Xing ^[3] ; Zhang, Lianzhu ^[4]

Afiliação do(s) autor(es)

^[1] Minnan Normal Univ, Sch Math & Stat, Zhangzhou - Peoples R China

^[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

^[3] Jiangxi Univ Sci & Technol, Fac Sci, Ganzhou - Peoples R China

^[4] Xiamen Univ, Sch Math Sci, Xiamen, Fujian - Peoples R China

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 343, n. 8 AUG 2020.
• Citações Web of Science: 0

Resumo

A connected graph G, of order two or more, is matching covered if each edge lies in some perfect matching. The tight cut decomposition of a matching covered graph G yields a list of bricks and braces; as per a theorem of Lovasz (1987), this list is unique (up to multiple edges); b(G) denotes the number of bricks, and c(4)(G) denotes the number of braces that are isomorphic to the cycle C-4 (up to multiple edges). Two edges e and f are mutually dependent if, for each perfect matching M, e is an element of M if and only if f is an element of M; Carvalho, Lucchesi and Murty investigated this notion in their landmark paper (Carvalho et al., 1999). For any matching covered graph G, mutual dependence is an equivalence relation, and it partitions E(G) into equivalence classes; this equivalence class partition is denoted by epsilon(G) and we refer to its parts as equivalence classes of G; we use epsilon(G) to denote the cardinality of the largest equivalence class. The operation of `splicing' may be used to construct bigger matching covered graphs from smaller ones; see {[}8] ; tight splicing' is a stronger version of `splicing'. (These are converses of the notions of `separating cut' and `tight cut'.) In this article, we answer the following basic question: if a matching covered graph G is obtained by `splicing' (or by tight splicing') two smaller matching covered graphs, say G(1) and G(2), then how is epsilon(G) related to epsilon(G1) and to epsilon(G2), (and vice versa)? As applications of our findings: firstly, we establish tight upper bounds on epsilon(G) in terms of b(G) and c(4)(G); secondly, we answer a recent question of He et al. (2019), in the affirmative, by constructing graphs that have arbitrarily high kappa(G) and epsilon(G) simultaneously, where kappa(G) denotes the vertex-connectivity. (C) 2020 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 18/04679-1 - Menores conformes e orientações Pfaffianas
• Beneficiário: Nishad Bharat Kothari
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado