Search

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]

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: 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: 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]

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]

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: 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]