Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

For any n 1 and any k 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 O(n) time. It is also shown that for k 3, the graphs S(n, k) are Hamiltonian.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

On Idomatic Partitions of Direct Products of Complete Graphs

Independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T ₁-sets, are explicitly described. It is proved that the direct product of four complete graphs admits an idomatic partition into T ₁-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Vertex and Edge Orbits of Fibonacci and Lucas Cubes

The Fibonacci cube \({\Gamma_{n}}\) is obtained from the n-cube Q _n by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube \({\Lambda_{n}}\) is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of vertex orbit sizes of \({\Lambda_{n}}\) is \({\{k \geq 1; k |n\} \cup \{k \geq 18; k |2n\}}\), the number of vertex orbits of \({\Lambda_{n}}\) of size k, where k is odd and divides n, is equal to \({\sum_{d | k} \mu (\frac{k}{d})F_{\lfloor{\frac{d}{2}}\rfloor+2}}\), and the number of edge orbits of \({\Lambda_{n}}\) is equal to the number of vertex orbits of \({\Gamma_{n-3}}\). Dihedral transformations of strings and primitive strings are essential tools to prove these results.     

On the role of hypercubes in the resonance graphs of benzenoid graphs

The resonance graph R(B) of a benzenoid graph B has the perfect matchings of B as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of B. A family P of pair-wise disjoint hexagons of a benzenoid graph B is resonant in B if B-P contains at least one perfect matching, or if B-P is empty. It is proven that there exists a surjective map f from the set of hypercubes of R(B) onto the resonant sets of B such that a k-dimensional hypercube is mapped into a resonant set of cardinality k.