Connected (C₄,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs

Abstract: A diamond is the graph that is obtained from removing an edge from the complete graph on

4

vertices. A (

C_{4}

,diamond)-free graph is a graph that does not contain a diamond or a cycle on four vertices as induced subgraphs. Let

G

be a connected (

C_{4}

,diamond)-free graph on

n

vertices. Let

1 l e k l e n - 1

be an integer. The

k

-token graph,

F_{k} (G)

, of

G

is the graph whose vertices are all the sets of

k

vertices of

G

; two of which are adjacent if their symmetric difference is a pair of adjacent vertices in

G

. Let

F

be a graph isomorphic to

F_{k} (G)

. In this paper we show that given only

F

, we can construct in polynomial time a graph isomorphic to

G

. Let

o p e r a t o r n a m e A u t (G)

be the automorphism group of

G

. We also show that if

k e q n / 2

, then

o p e r a t o r n a m e A u t (G) s i m e q o p e r a t o r n a m e A u t (F_{k} (G))

; and if

k = n / 2

, then

o p e r a t o r n a m e A u t (G) s i m e q o p e r a t o r n a m e A u t (F_{k} (G)) i m e s m a t h b b Z_{2}

.

This page was built for publication: Connected ($C_4$,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs