A matching in a graph G = (V, E) is a set M ⊆ E, such that no two edges in M share an endvertex. An edge cut in G is a set of edges C ⊆ E, such that we can partition V into two non-empty sets R and B, where C is the set of edges with one endvertex in R and one in B. A matching cut is a set of edges M ⊆ E which is both a matching and an edge cut. In this thesis, we consider the decision problems Matching Cut, its variants Disconnected Perfect Matching and Perfect Matching Cut, as well as its generalisation d-Cut. We give polynomial time algorithms and NP-completeness results for certain graph classes, including H-free graphs, for some graphs H, and graphs of bounded radius and diameter. In particular, we solve a 20-year old open problem by showing the NP-completeness of Matching Cut for graphs of high girth. We also consider the maximisation version Maximum Matching Cut, where we ask for a matching cut of maximum size, that is with the maximum number of edges in the matching cut. For this variant we give a complexity dichotomy for graphs of bounded radius, bounded diameter, H-free graphs and bipartite graphs of bounded radius and diameter. We conclude with a comparison of all variants, which allows to identify interesting open problems.
The study of graph connectedness is a central topic in graph theory, with CF-connectedness being a specialized property of interest. A simple graph is CF-connected if it is connected and, in each of its optimal drawings, any two of its distinct vertices can be connected by a path consisting of uncrossed edges. This pap...
M. Staš, M. Švecová, Jana Fortes· Mathematics· 0 citations
An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $\rho_e^o(G)=\...
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for com...
I. Dumitru, Adrian Miclaus, Alexandru Popa· 0 citations
Given a simple and undirected graph G=(V(G),E(G)). Then R\subseteq V(G) is called a 2-distance certified independent set of G if R satisfies the following two conditions:(i)For every x\in R, x has either zero or at least two hop neighborhood in V(G)\setminus R; and (ii) R is an independent set of
G. The 2-distance cer...
Javier Hassan, Radzkhan B. Berte· International Journal of Mat...· 0 citations
In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that...
Sourav Das, Ashwin Jacob, Arpit Kumar et al.· 0 citations
A connected graph $G$ with at least two vertices is {\em matching covered} if each of its edges lies in a perfect matching. A matching covered graph is {\em minimal} if the removal of any edge results in a graph that is no longer matching covered. Lov\'asz and Plummer [J. Combin. Theory, Ser. B 23 (1977) 127--138] prov...
Xiao-Ling He· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
