A connected simple graph G is called $k$--cohesive if for any pair of distinct vertices $u,v \in V(G)$, $d(u) + d(v) + d(u,v) \ge k$. A subgraph $H$ of a connected graph $G$ is non-separating if $G -V(H)$ is connected. Locke [MAA Monthly - 1998] conjectured that given a tree $T$ on $n$ vertices, $n \ge 3$, any $2n$--cohesive graph has a non-separating copy of $T$. Here we prove that given a tree $T$ on $n$ vertices and diameter at most 4, any $(2n + 2)$--cohesive graph has a non-separating copy of $T$.
Nonseparating n-trees of diameter at most 4 in (2n+2)-cohesive graphs.
ABREU, Marien;
2002-01-01
Abstract
A connected simple graph G is called $k$--cohesive if for any pair of distinct vertices $u,v \in V(G)$, $d(u) + d(v) + d(u,v) \ge k$. A subgraph $H$ of a connected graph $G$ is non-separating if $G -V(H)$ is connected. Locke [MAA Monthly - 1998] conjectured that given a tree $T$ on $n$ vertices, $n \ge 3$, any $2n$--cohesive graph has a non-separating copy of $T$. Here we prove that given a tree $T$ on $n$ vertices and diameter at most 4, any $(2n + 2)$--cohesive graph has a non-separating copy of $T$.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.
