SSD Set System, Graph Decomposition and Hamiltonian Cycle
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909325006471168 |
|---|---|
| author | Shota, Kan Haraguchi, Kazuya |
| author_facet | Shota, Kan Haraguchi, Kazuya |
| contents | In this paper, we first study what we call Superset-Subset-Disjoint (SSD) set system. Based on properties of SSD set system, we derive the following (I) to (IV):
(I) For a nonnegative integer $k$ and a graph $G=(V,E)$ with $|V|\ge2$, let $X_1,X_2,\dots,X_q\subsetneq V$ denote all maximal proper subsets of $V$ that induce $k$-edge-connected subgraphs. Then at least one of (a) and (b) holds: (a) $\{X_1,X_2,\dots,X_q\}$ is a partition of $V$; and (b) $V\setminus X_1, V\setminus X_2,\dots,V\setminus X_q$ are pairwise disjoint.
(II) For $k=1$ and a strongly-connected digraph $G$, whether $V$ is in (a) and/or (b) can be decided in $O(n+m)$ time and we can generate all such $X_1,X_2,\dots,X_q$ in $O(n+m+|X_1|+|X_2|+\dots+|X_q|)$ time, where $n=|V|$ and $m=|E|$.
(III) For a digraph $G$, we can enumerate in linear delay all vertex subsets of $V$ that induce strongly-connected subgraphs.
(IV) A digraph is Hamiltonian if there is a spanning subgraph that is strongly-connected and in the case (a). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04615 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | SSD Set System, Graph Decomposition and Hamiltonian Cycle Shota, Kan Haraguchi, Kazuya Data Structures and Algorithms Discrete Mathematics Combinatorics G.2.1; G.2.2 In this paper, we first study what we call Superset-Subset-Disjoint (SSD) set system. Based on properties of SSD set system, we derive the following (I) to (IV): (I) For a nonnegative integer $k$ and a graph $G=(V,E)$ with $|V|\ge2$, let $X_1,X_2,\dots,X_q\subsetneq V$ denote all maximal proper subsets of $V$ that induce $k$-edge-connected subgraphs. Then at least one of (a) and (b) holds: (a) $\{X_1,X_2,\dots,X_q\}$ is a partition of $V$; and (b) $V\setminus X_1, V\setminus X_2,\dots,V\setminus X_q$ are pairwise disjoint. (II) For $k=1$ and a strongly-connected digraph $G$, whether $V$ is in (a) and/or (b) can be decided in $O(n+m)$ time and we can generate all such $X_1,X_2,\dots,X_q$ in $O(n+m+|X_1|+|X_2|+\dots+|X_q|)$ time, where $n=|V|$ and $m=|E|$. (III) For a digraph $G$, we can enumerate in linear delay all vertex subsets of $V$ that induce strongly-connected subgraphs. (IV) A digraph is Hamiltonian if there is a spanning subgraph that is strongly-connected and in the case (a). |
| title | SSD Set System, Graph Decomposition and Hamiltonian Cycle |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2408.04615 |