Two-ended regular median graphs

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 G the condition of linear growth can be weakened to the condition that G 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.     

On compact median graphs

A median graph is called compact if it does not contain an isometric ray. This property is shown to be equivalent to the finite intersection property for convex sets. We show that a compact median graph contains a finite cube that is fixed by all of its automorphisms, and that each family of commuting endomorphisms of a compact median graph fixes a common cube. © 1996 John Wiley & Sons, Inc.     

Hyperbolicity in median graphs

If X is a geodesic metric space and x ₁,x ₂,x ₃?∈?X, a geodesic triangle T?=?{x ₁,x ₂,x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e., ${\delta}(X)=\inf\{{\delta}\ge 0: \, X \, \text{is $\delta$-hyperbolic}\}. $ In this paper we study the hyperbolicity of median graphs and we also obtain some results about general hyperbolic graphs. In particular, we prove that a median graph is hyperbolic if and only if its bigons are thin.     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

On graphs with prescribed median I

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f(G) denote the minimum order of a connected graph H satisfying M(H) ? G. It is shown that if G has n vertices and minimum degree δ then f(G) ? 2n ? δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K_r are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x 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 G whose remoteness function is maximum (antimedian set of G) 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 G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.     

On the geodetic number of median graphs

A set of vertices S in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from S. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Dominating sets in n-cubes

A perfectdominatingset S of a graph Γ is a set of vertices of Γ such that every vertex of Γ is either in S or is adjacent to exactly one vertex of S. We show that a perfect dominating set of the n-cube Q_n induces a subgraph of Q_n whose components are isomorphic to hypercubes. We conjecture that each of these hypercubes has the same dimension. We then prove that if Q_r is a component of the subgraph induced by S, then n ? r ? 1 or 3 (mod 6). A number of examples are given and connections with Steiner Systems and codes are noted.     

The median function on graphs with bounded profiles

The median of a profile π=(u₁,…,u_k) of vertices of a graph G is the set of vertices x that minimize the sum of distances from x to the vertices of π. It is shown that for profiles π with diameter θ the median set can be computed within an isometric subgraph of G that contains a vertex x of π and the r-ball around x, where r>2θ−1−2θ/|π|. The median index of a graph and r-joins of graphs are introduced and it is shown that r-joins preserve the property of having a large median index. Consensus strategies are also briefly discussed on a graph with bounded profiles.     

A Volume-diameter inequality for n-cubes

Conclusion Several problems still remain open. It would be very interesting if a proof of Theorem (3.5) could be obtained without the requirement that the functiong be Lipschitzian; this condition being required in order to guarantee thatA be sufficiently smooth. An analogue of Theorem (3.5) using interior distance should also be possible. Moreover, Theorem (4.8) should extend to the continuous case. Analogues of these theorems using weighted distances probably would have meaningful applications in the study of extremal length. This work was partially supported by NSF grant GP-4071, and was submitted as a doctoral dissertation at Indiana University.     

Infinite median graphs, (0, 2)-graphs,and hypercubes

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)-graphs are hypercubes. No cardinality restrictions are made.     

On a class of lattices associated with n-cubes

A Lattice L(X) is defined starting from a cubical lattice L and an increasing diagonally closed subset X of L (Section 1). The lattice L(X) are proved to be—up to isomorphism—precisely those of signed simplexes of a simplical complex (Section 2); furthermore, an algebraic combinatorial characterization of the lattices L(X) is given (Section 3).     

On the decomposition of n-cubes into isomorphic trees

We prove that if T is any tree having n edges (n ≥ 1), then the n-cube Q_n can be decomposed into 2^n-1 edge-disjoint induced subgraphs, each of which is isomorphic to T. We use this statement to obtain two results concerning decompositions of Q_n into subgraphs isomorphic to members of a specified family of trees.