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.

#### 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$.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
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/11563/8935
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• ND