Search

Let H be an arbitrary graph with vertex set V (H) = [nH] = {1, ...,nH}. The generalized Sierpiriski graph SHn, n ∈ ℕ, is defined on the vertex set [nH]n, two different vertices u = un ... u1 and v = vn ... v1 being adjacent if there exists an h e [n] such that (a) ut = vt, for t > h, (b) uh ≠ vh and uhvh ∈ E(H), and (c) ut = vh and vt = uh for t < h. If H is the complete graph Kk, then we speak of the Sierpiński graph Skn. We present an algorithm that recognizes Sierpiński graphs Skn in O(|V(Sn )|1+1/n) = O(|E(Skn)|) time. For generalized Sierpiński graphs SH we present a polynomial time algorithm for the case when H belong to a certain well defined class of graphs. We also describe how to derive the base graph H from an arbitrarily given SHn. [ABSTRACT FROM AUTHOR]

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G o H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G o H is non-trivial and complete, then G o H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph. [ABSTRACT FROM AUTHOR]

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]