Spanning caterpillar in biconvex bipartite graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910466529296384 |
|---|---|
| author | Antony, Dhanyamol Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| author_facet | Antony, Dhanyamol Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| contents | A bipartite graph $G=(A, B, E)$ is said to be a biconvex bipartite graph if there exist orderings $<_A$ in $A$ and $<_B$ in $B$ such that the neighbors of every vertex in $A$ are consecutive with respect to $<_B$ and the neighbors of every vertex in $B$ are consecutive with respect to $<_A$. A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this note, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph. Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_10956 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Spanning caterpillar in biconvex bipartite graphs Antony, Dhanyamol Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka Combinatorics Discrete Mathematics 05C75, 05C05 A bipartite graph $G=(A, B, E)$ is said to be a biconvex bipartite graph if there exist orderings $<_A$ in $A$ and $<_B$ in $B$ such that the neighbors of every vertex in $A$ are consecutive with respect to $<_B$ and the neighbors of every vertex in $B$ are consecutive with respect to $<_A$. A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this note, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph. Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs. |
| title | Spanning caterpillar in biconvex bipartite graphs |
| topic | Combinatorics Discrete Mathematics 05C75, 05C05 |
| url | https://arxiv.org/abs/2312.10956 |