 Cycle-connected mixed graphs and related problemsJunran Lichen ()
Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 49, 19 pages Abstract: Abstract In this paper, motivated by applications of vertex connectivity of digraphs or graphs, we consider the cycle-connected mixed graph (CCMG, for short) problem, which is in essence different from the connected mixed graph (CMG, for short) problem, and it is modelled as follows. Given a mixed graph $$G=(V,A\cup E)$$ G = ( V , A ∪ E ) , for each pair $$ \{u, v\}$$ { u , v } of two distinct vertices in G, we are asked to determine whether there exists a mixed cycle C in G to contain such two vertices u and v, where C passes through its arc (x, y) along the direction only from x to y and its edge xy along one direction either from x to y or from y to x. Particularly, when the CCMG problem is specialized to either digraphs or graphs, we refer to the related version of the CCMG problem as either the cycle-connected digraph (CCD, for short) problem or the cycle-connected graph (CCG, for short) problem, respectively, where such a graph in the CCG problem is called as a cycle-connected graph. Similarly, we consider the weakly cycle-connected (in other words, circuit-connected) mixed graph (WCCMG, for short) problem, only substituting a mixed circuit for a mixed cycle in the CCMG problem. Moreover, given a graph $$G=(V,E)$$ G = ( V , E ) , we define the cycle-connectivity $$\kappa _c(G)$$ κ c ( G ) of G to be the smallest number of vertices (in G) whose deletion causes the reduced subgraph either not to be a cycle-connected graph or to become an isolated vertex; Furthermore, for each pair $$\{s, t\}$$ { s , t } of two distinct vertices in G, we denote by $$\kappa _{sc}(s,t)$$ κ sc ( s , t ) the maximum number of internally vertex-disjoint cycles in G to only contain such two vertices s and t in common, then we define the strong cycle-connectivity $$\kappa _{sc}(G)$$ κ sc ( G ) of G to be the smallest of these numbers $$\kappa _{sc}(s,t)$$ κ sc ( s , t ) among all pairs $$\{s, t\}$$ { s , t } of distinct vertices in G. We obtain the following three results. (1) Using a transformation from the directed 2-linkage problem, which is NP-complete, to the CCD problem, we prove that the CCD problem is NP-complete, implying that the CCMG problem still remains NP-complete, and however, we design a combinatorial algorithm in time $$O(n^2m)$$ O ( n 2 m ) to solve the CCG problem, where n is the number of vertices and m is the number of edges of a graph $$G=(V,E)$$ G = ( V , E ) ; (2) We provide a combinatorial algorithm in time O(m) to solve the WCCMG problem, where m is the number of edges of a mixed graph $$G=(V,A\cup E)$$ G = ( V , A ∪ E ) ; (3) Given a graph $$G=(V,E)$$ G = ( V , E ) , we present twin combinatorial algorithms to compute cycle-connectivity $$\kappa _c(G)$$ κ c ( G ) and strong cycle-connectivity $$\kappa _{sc}(G)$$ κ sc ( G ) , respectively. Keywords: Combinatorial optimization; Cycle-connected mixed graphs; Circuit-connected mixed graphs; Cycle-connectivity; Combinatorial algorithms (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00979-3 Ordering information: This journal article can be ordered from DOI: 10.1007/s10878-022-00979-3 Access Statistics for this article Journal of Combinatorial Optimization is currently edited by Thai, My T. More articles in Journal of Combinatorial Optimization from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.