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]

Abstract: The problem of recognizing approximate graph products arises in theoretical biology. This paper presents an algorithm that recognizes a large class of approximate graph products. The main part of this contribution is concerned with a new, local prime factorization algorithm that factorizes all strong products on an extensive class of graphs that contains, in particular, all products of triangle-free graphs on at least three vertices. The local approach is linear for graph with fixed maximal degree. [Copyright &y& Elsevier]

Abstract: We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331–349], who compute the prime factors in time, where m denotes the number of vertices of G and n the number of edges. Our algorithm is conceptually simpler. It gains its efficiency by the introduction of edge-labellings. [Copyright &y& Elsevier]

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]

Let M(m, n) be the complexity of checking whether a graph G with m edges and n vertices is a median graph. We show that the complexity of checking whether G is triangle-free is at most O(M(m, m)). Conversely, we prove that the complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n, n)), where T(m, n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, there are as many median graphs as there are triangle-free graphs. Finally, these results enable us to prove that the complexity of recognizing planar median graphs is linear. [ABSTRACT FROM AUTHOR]

Abstract: This note extends results of Fernández, Leighton, and López-Presa on the uniqueness of th roots for disconnected graphs with respect to the Cartesian product to other products and shows that their methods also imply new cancelation laws. [Copyright &y& Elsevier]