EuDML | Browse

We prove that for every number $n \geq 1$ , the $n$ -iterated $P_{3}$ -path graph of $G$ is isomorphic to $G$ if and only if $G$ is a collection of cycles, each of length at least 4. Hence, $G$ is isomorphic to $P_{3} (G)$ if and only if $G$ is a collection of cycles, each of length at least 4. Moreover, for $k \geq 4$ we reduce the problem of characterizing graphs $G$ such that $P_{k} (G) ≅ G$ to graphs without cycles of length exceeding $k$ .

Graphs of diameter 2 with cyclic defect

S. Fajtlowicz (1987)

Colloquium Mathematicae

Graphs $S (n, k)$ and a variant of the Tower of Hanoi problem

Sandi Klavžar, Uroš Milutinović (1997)

Czechoslovak Mathematical Journal

For any $n \geq 1$ and any $k \geq 1$ , a graph $S (n, k)$ is introduced. Vertices of $S (n, k)$ are $n$ -tuples over ${1, 2, ..., k}$ and two $n$ -tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs $S (n, 3)$ are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of $S (n, k)$ . Together with a formula for the distance, this result is used to compute the distance between two vertices in...

Displaying 1 – 14 of 14

Generalized Ramsey numbers for paths in 2-chromatic graphs.

Geodesics and steps in a connected graph

Geography played on an $n$ -cycle times a 4-cycle.

Graph cycles and diagram commutativity

Graph equations for line graphs and n-th distance graphs.

Graph invariants and large cycles: a survey.

Graphes sans circuit et bilinéarité

Graphs isomorphic to their path graphs

Graphs of diameter 2 with cyclic defect

Graphs $S (n, k)$ and a variant of the Tower of Hanoi problem

Graphs which are locally paths

Graphs which have pancyclic complements.

Graphs with a given edge neighbourhood

Gray codes in graphs

Currently displaying 1 – 14 of 14