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$.
2023
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]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2940211
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact