2019/02/25 by Fuliang Lu, Lu, Fuliang, Nishad Kothari +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1902.09260
openalex publication_date 2019/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A connected graph G, of order two or more, is matching covered if each edge lies in some \pema. The tight cut decomposition of a matching covered graph G yields a list of bricks and braces; as per a theorem of Lovász~\citelova87, this list is unique (up to multiple edges); b(G) denotes the number of bricks, and c4(G) denotes the number of braces that are isomorphic to the cycle C4 (up to multiple edges). Two edges e and f are mutually dependent if, for each perfect matching M, e ∈ M if and only if f ∈ M; Carvalho, Lucchesi and Murty investigated this notion in their landmark paper~\citeclm99. 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 EG and we refer to its parts as equivalence classes of G; we use ε(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~\citelckm18; `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~G1~and~G2, then how is EG related to EG1 and to EG2 (and vice versa)? As applications of our findings: firstly, we establish tight upper bounds on ε(G) in terms of b(G) and c4(G); secondly, we answer a recent question of He, Wei, Ye and Zhai~\citehwyz19, in the affirmative, by constructing graphs that have arbitrarily high κ(G)~and~ε(G) simultaneously, where κ(G) denotes the vertex-connectivity.