We make progress toward a characterization of the graphs $H$ such that every connected $H$-free graph has a longest path transversal of size $1$. In particular, we show that the graphs $H$ on at most $4$ vertices satisfying this property are exactly the linear forests. We also show that if the order of a connected graph $G$ is large relative to its connectivity $\kappa(G)$, and its independence number $\alpha(G)$ satisfies $\alpha(G) \le \kappa(G) + 2$, then each vertex of maximum degree forms a longest path transversal of size $1$.
Non-empty intersection of longest paths in H-free graphs / Long, J. A.; Milans, K. G.; Munaro, A.. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - 30:1(2023). [10.37236/11277]
Non-empty intersection of longest paths in H-free graphs
Munaro A.
2023-01-01
Abstract
We make progress toward a characterization of the graphs $H$ such that every connected $H$-free graph has a longest path transversal of size $1$. In particular, we show that the graphs $H$ on at most $4$ vertices satisfying this property are exactly the linear forests. We also show that if the order of a connected graph $G$ is large relative to its connectivity $\kappa(G)$, and its independence number $\alpha(G)$ satisfies $\alpha(G) \le \kappa(G) + 2$, then each vertex of maximum degree forms a longest path transversal of size $1$.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.