Article in press
Authors:
Title:
The structure of 2-matching connected graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-09-17 , Revised: 2024-06-27 , Accepted: 2024-07-02 , Available online: 2024-07-16 , https://doi.org/10.7151/dmgt.2552
Abstract:
Constructive characterizations of classical connectivity have been studied by
many researchers. Whitney states that a graph is $2$-connected if and only if
it is a cycle or can be obtained from a cycle by repeatedly adding ears. Tutte
asserts that a graph is $3$-connected if and only if it is a wheel or can be
obtained from a wheel by repeatedly adding edges and splitting vertices of
degree more than three. Slater determines that the class of $4$-connected graphs
is the class of graphs obtained from $K_5$ by finite sequences of edge addition,
$4$-soldering, $4$-vertex-splitting, $4$-edge-splitting, and
$3$-fold-$4$-vertex-splitting. For an integer $k$, a graph $G$ is
$k$-matching connected if $G-V(M)$ is a connected nontrivial graph for
each matching $M$ with $|M|\leq k-1$, where $V(M)$ is the set of vertices
covered by $M$. In this paper, we present that a graph $G$ is $2$-matching
connected if and only if either $G\in\{C_4, K_4\}$ or it can be obtained from
a $C_4$ by repeatedly applying the following three operations.
- (i) Adding a new edge $uv$ for a pair of nonadjacent vertices $u$ and $v$ where $\{u,v\}$ is not a vertex cut of $G$.
- (ii) Adding an ear $uwv$, where $w$ is a new vertex and $u, v$ are a pair of nonadjacent vertices of $G$.
- (iii) Replacing a vertex $z$ by two new adjacent vertices $z_1$ and $z_2$, and making $z_i$ adjacent to every vertex of $N_i$ such that $d(z_i)\geq 2$ for $i\in \{1,2\}$, where $N_1\cup N_2=N(z)$ and $N_1\cap N_2=\emptyset.$
Keywords:
matching, connectivity, matching-connectivity, graph characterization
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - A.-H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199.
https://doi.org/10.1016/0020-0190(88)90025-7 - A.-H. Esfahanian, Generalized measures of fault tolerance with application to $N$-cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591.
https://doi.org/10.1109/12.42131 - J. Fàbrega and M.A. Fiol, On the extraconnectivity of graphs, Discrete Math. 155 (1996) 49–57.
https://doi.org/10.1016/0012-365X(94)00369-T - F. Harary, Conditional connectivity, Networks 13 (1983) 347–357.
https://doi.org/10.1002/net.3230130303 - S. Latifi, M. Hegde and M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222.
https://doi.org/10.1109/12.262126 - H. Li, M. Ma, S. Zhao, X. Zhao, X. Hua, Y. Ma and H. Lai, The matching-connectivity of a graph, submitted.
- C.-K. Lin, L. Zhang, J. Fan and D. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoret. Comput. Sci. 634 (2016) 97–107.
https://doi.org/10.1016/j.tcs.2016.04.014 - O.R. Oellermann, The connected cutset connectivity of a graph, Discrete Math. 69 (1988) 301–308.
https://doi.org/10.1016/0012-365X(88)90058-1 - T. Politof and A. Satyanarayana, The structure of quasi $4$-connected graphs, Discrete Math. 161 (1996) 217–228.
https://doi.org/10.1016/0012-365X(95)00229-P - P.J. Slater, A classification of $4$-connected graphs, J. Combin. Theory Ser. B 17 (1974) 281–298.
https://doi.org/10.1016/0095-8956(74)90034-3 - W.T. Tutte, A theory of $3$-connected graphs, Indag. Math. 64 (1961) 441–455.
https://doi.org/10.1016/S1385-7258(61)50045-5 - H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150–168.
https://doi.org/10.2307/2371086
Close