Square-free Walks on Labelled Graphs

Details Square-free Walks on Labelled Graphs Square-free Walks on Labelled Graphs

2011-06-21

arxiv.org/abs/1106.4106v2

Mathematics

Combinatorics

Scientific paper

A finite or infinite word is called a $G$-word for a labelled graph $G$ on the vertex set $A_n = \{0,1,..., n-1\}$ if $w = i_1i_2...i_k \in A_n^*$, where each factor $i_ji_{j+1}$ is an edge of $E$, i.e, $w$ represents a walk in $G$. We show that there exists a square-free infinite $G$-word if and only if $G$ has no subgraph isomorphic to one of the cycles $C_3, \ C_4, \ C_5$, the path $P_5$ or the claw $K_{1,3}$. The colour number $\gamma(G)$ of a graph $G=(A_n,E)$ is the smallest integer $k$, if it exists, for which there exists a mapping $\phi\colon A_n \to A_k$ such that $\phi(w)$ is square-free for an infinite $G$-word $w$. We show that $\gamma(G)=3$ for $G=C_3, C_5, P_5$, but $\gamma(G)=4$ for $G=C_4, K_{1,3}$. In particular, $\gamma(G) \leq 4$ for all graphs that have at least five vertices.

Affiliated with

Also associated with

No associations

Rating

Square-free Walks on Labelled Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Square-free Walks on Labelled Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Square-free Walks on Labelled Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-177914