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]

We extend results about asymmetric colorings of finite Cartesian products of graphs to strong and direct products of graphs and digraphs. On the way we shorten proofs for the existence of prime factorizations of finite digraphs and characterize the structure of the automorphism groups of strong and direct products. The paper ends with results on asymmetric colorings of Cartesian products of finite and infinite digraphs. [ABSTRACT FROM AUTHOR]

The distinguishing number D(G) of a graph G is the minimum number of colors needed to color the vertices of G such that the coloring is preserved only by the trivial automorphism. In this paper we improve results about the distinguishing number of Cartesian products of finite and infinite graphs by removing restrictions to prime or relatively prime factors. [ABSTRACT FROM AUTHOR]

The boxicity ( cubicity ) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R k . In this article, we give estimates on the boxicity and the cubicity of Cartesian , strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d , of the boxicity and the cubicity of the d th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the d th Cartesian power of any given finite graph is, respectively, in O ( log d / log log d ) and Θ ( d / log d ) . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. [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]

Abstract: We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends. For cubic median graphs the condition of linear growth can be weakened to the condition that has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth. [Copyright &y& Elsevier]

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1, 3, 5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: This note presents a linear algorithm that isometrically embeds a given tree into an integer lattice of minimal dimension and allows one to compute the lattice coordinates of every single vertex of in optimal time. [Copyright &y& Elsevier]

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]

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. [ABSTRACT FROM AUTHOR]

Abstract: A graph may be the Kronecker cover in more than one way. In this note we explore this phenomenon and apply it to show that the minimal common cover of two graphs need not be unique. We provide examples of graphs of the same size with non-unique common double covers and of isovalent graphs of the same size with non-unique minimal regular common covers. [Copyright &y& Elsevier]

Abstract: The distinguishing number of a graph is the least integer such that has a labeling with labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product for all and , either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs. [Copyright &y& Elsevier]

By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time. [ABSTRACT FROM AUTHOR]

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]

Abstract: In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in time, where n denotes the number of vertices and m the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time. [Copyright &y& Elsevier]

Abstract: A graph polynomial is called reconstructible if it is uniquely determined by the polynomials of the vertex-deleted subgraphs of G for every graph G with at least three vertices. In this note it is shown that subgraph-counting graph polynomials of increasing families of graphs are reconstructible if and only if each graph from the corresponding defining family is reconstructible from its polynomial deck. In particular, we prove that the cube polynomial is reconstructible. Other reconstructible polynomials are the clique, the path and the independence polynomials. Along the way two new characterizations of hypercubes are obtained. [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]

If a graph G has distinguishing number 2, then there exists a partition of its vertex set into two parts, such that no nontrivial automorphism of G fixes setwise the two parts. Such a partition is called a 2- distinguishing coloring of G , and the parts are called its color classes. If G admits such a coloring, it is often possible to find another in which one of the color classes is sparse in a certain sense. In this case we say that G has 2- distinguishing density zero. An extreme example of this would be an infinite graph admitting a 2-distinguishing coloring in which one of the color classes is finite. The Infinite Motion Conjecture is a well-known open conjecture about 2-distinguishability. A graph G is said to have infinite motion if every nontrivial automorphism of G moves infinitely many vertices, and the conjecture states that every connected, locally finite graph with infinite motion is 2-distinguishable. In this paper we show that for many classes of graphs for which the Infinite Motion Conjecture is known to hold, the graphs have 2-distinguishing density zero. [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]

Abstract: A profile on a graph is any nonempty multiset whose elements are vertices from . The corresponding remoteness function associates to each vertex the sum of distances from to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph whose remoteness function is maximum (antimedian set of ) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph on vertices and edges, decides in time whether is a median graph with geodetic number 2. [Copyright &y& Elsevier]