Skip to content
DraconiticResearch
Search Sources API
186,631 studies31 sourcesUpdated 17 min ago
PreprintarXiv licencearXiv

Two characterizations of chain partitioned probe graphs

  • Van Bang Le
Open at sourcePDFDOICite

Abstract

Chain graphs are exactly bipartite graphs without induced 2K2 (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆ V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. %there exists a set E'⊆binomS2 such that the graph G'=(V,E∪ E') is a chain graph. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain ``enhanced graph'': G is a chain partitioned probe graph if and only if the enhanced graph G* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m2)-time recognition algorithm for chain partitioned probe graphs.

Versions

Related

  1. Reduction Operations and Characterizations of S1-Flows in Graphs
    Chenxing Li, Jiaao Li, Rong Luo +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Structural Characterizations and Algebraic Realizations of a Family of Regular Integral Graphs
    Tapa Manna, Supriyo Dutta, Baby Bhattacharya
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs
    Ahmet Batal
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the generalized cospectral mates of chain graphs of rank 4
    Wei Wang, Siqi Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Fast and Scalable Multi-Agent Distribution Matching via Partitioned Optimal Transport
    Kooktae Lee, Ruchika Singh
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{le2026characterizations,
  title = {{Two characterizations of chain partitioned probe graphs}},
  author = {Van Bang Le},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23965},
  eprint = {2610.23965},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23965},
}
RIS
TY  - UNPB
TI  - Two characterizations of chain partitioned probe graphs
AU  - Van Bang Le
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.23965
UR  - https://arxiv.org/abs/2610.23965
AB  - Chain graphs are exactly bipartite graphs without induced 2K_2 (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆ V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. %there exists a set E'⊆binomS2 such that the graph G'=(V,E∪ E') is a chain graph. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain ``enhanced graph'': G is a chain partitioned probe graph if and only if the enhanced graph G^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m^2)-time recognition algorithm for chain partitioned probe graphs.
ER  -