Axiomatic characterization of the interval function of partial cubes and partial Hamming graphs

Abstract

Interval function of a graph is a well-known notion in metric graph theory and the axiomatic characterization using a set of first order axioms of different graph classes is an interesting problem in this area. Partial cubes and partial Hamming graphs form one of the central graph class that can be embedded into hypercubes and Hamming graphs respectively. In this paper we present an axiomatic characterization of the interval function of partial cubes and partial Hamming graphs, using different first order axioms. Further, we give an axiomatic characterization of the interval function of these graphs using axioms on an arbitrary function R on V.

Keywords:

• Partial Hamming graph
• partial cube
• interval function
• transit function

1 Introduction

The Hamming graphs, introduced by Richard Hamming, are the Cartesian product of complete graphs. In the bipartite case these graphs become the well known hypercubes; the Cartesian product of $K_2$’s. Graphs that are isometrically embeddable into a Hamming graph are called partial Hamming graphs. Alternatively, G is a partial Hamming graph if each vertex of G can be labeled by a word of fixed length over some alphabet such that the distance between any two vertices of G is equal to the Hamming distance between the corresponding words. Hamming graphs and partial Hamming graphs appear in several branches of mathematics and have applications in real world and other branches of science.

Partial Hamming graphs have been first studied by Winkler [27] and later, Chepoi [12] and Wilkiet [26] proved several characterizations of these graphs. In [27], it is proved that any two isometric embedding of a graph into a Hamming graph are equivalent. Using this result, a simple $O(n^5)$ algorithm, called Winkler’s algorithm, for recognizing partial Hamming graphs was also presented. Later, Wilkeit [26] gave an $O(n^3)$ recognition algorithm and in 1993 Imrich and Klavžar [18] and in 1994 Aurenhammer [1] gave an $O(mn)$ algorithm. The class of quasi-median graphs, which include cliques and block graphs, and the class of weakly median graphs are non-bipartite partial Hamming graphs, [26].

The partial cubes, also known as binary partial Hamming graphs are the bipartite partial Hamming graphs. Partial cubes were introduced by Graham and Pollak [17] and these graphs finds several applications in chemical graph theory [13]. Partial cubes were first characterized by Djoković in 1973 [14]. Further, Avis [2], Winkler [27], Roth and Winkler [24], Chepoi [10, 11] and Ovchinnikov [23] gave different characterizations. In [23], partial cubes are characterized using fundamental sets. Partial cubes comprise many essential and complex graph classes occurring in metric graph theory. Among them are the graphs of regions of hyperplane arrangements in ${\mathbb{R}}^d$, median graphs, netlike partial cubes and trees [25]. Another class of partial cubes extending median graphs is the class of ample graphs [4]. An $O(nm)$ time algorithm for the recognition of partial cubes is established in [18], while [15] presents an $O(n^2)$ timealgorithm.

Recently, Chalopin et al. [5] has developed a new approach in graph theory by presenting an axiomatization of the main classes of graphs occurring in metric graph theory using the First-Order Logic with Betweenness (FOLB). The main classes of graphs which possess such an axiomatization include the class of weakly modular graphs, partial cubes, Gromov hyperbolic graphs and the principal subclasses and superclasses of these graphs. It is proved in [5] that partial Hamming graphs and partial cubes are definable in FOLB.

Note that, in the model theory context, a graph property P is first-order definable if we can find a first-order formula $\varphi$, which holds exactly when P holds and the problem is solved by finding such a sentence $\varphi$. It is interesting to note that, if a graph class is definable using a set of first order axioms then it has a polynomial time recognition, but the converse need not be true, see [5].

In the approach initiated by Nebeský, Mulder, Sholander, Changat, etc. [6, 20, 21], the definability is presented along with a detailed proof by extending the characterization to an arbitrary transit function (or even in some cases for a function $R:V\times V\to 2^V$) defined on a nonempty set V. In fact, the latter’s approach is to find an independent and consistent axiomatic system for the corresponding graph class.

By an independent set of axioms we mean, no axiom of the set of axioms can be deduced from the remaining axioms of that set. A model of an axiomatic system is a way to define the undefined terms so that the axioms are true. An axiomatic system is consistent if there exists a model for the system. We do not want the axioms system to lead to contradictions, and we can check this by finding a model for the axioms.

In this paper, we follow the approach by Mulder and Nebeský and obtain axiomatic characterizations of the interval function of partial cubes and partial Hamming graphs. The axioms for the characterization are derived from the corresponding FOLB-queries characterizing the partial cubes and the partial Hamming graphs in [5] and we prove that the axiom system is independent and consistent.

A transit function is a general notion which is introduced to present a unifying approach for the results and ideas on intervals, convexities and betweenness in graphs and posets [19]. Given a non-empty set V, a transit function is defined as a function $R:V\times V\to 2^V$ satisfying the following three axioms: $$(t1)u\in R(u,v),\text{ for all}u,v\in V$$ $$(t2)R(u,v)=R(v,u),\text{ for all}u,v\in V$$ $$(t3)R(u,u)=\left\{u\right\},\text{ for all}u\in V$$

Prime examples of transit functions in graphs are interval function, induced path function and all-paths function. Cut-vertex transit function and the longest path function are other examples of interesting transit functions in graphs. Recently, new transit functions, named as toll function and its axiomatic characterizations on AT-free graphs and interval graphs were presented in [22]. The interval function I of a connected graph is a fundamental tool in problems that involve distance and shortest paths. Axiomatic studies on interval function of graphs is an important area in metric graph theory. The first systematic study on the interval function was by Mulder [21]. Axiomatic characterization of the interval function of arbitrary connected graphs has been first given by Nebeský and finally Mulder and Nebeský gave an optimal characterization in [20] (this is known as the Mulder-Nebeský theorem). Further, the study is extended to disconnected graph by Changat et al. [6].

Moreover, axiomatic characterization of the interval function of trees, block graphs, median graphs, modular graphs and geodetic graphs were studied, see [8] and [3]. Similar characterizations of the interval function of claw and paw-free graphs, bipartite graphs and forests have been obtained in [7, 9]. The present paper is motivated by these studies.

Next, we fix the graph theoretical notations and terminology that we follow in this paper. Throughout, we consider only finite, undirected, simple and connected graphs, denoted as $G=(V,E)$. More often, we may use the notation G for such a graph. We denote the standard shortest path metric in G by $d_G$ (or d if the graph G is evident).

The interval function denoted as I of a graph G is defined as the function $I:V\times V\to 2^V$ with $I(u,v)=\{w\in V:d(u,w)+d(w,v)=d(u,v)\}$ $=\{w\in V:w\text{ lies on some shortest }u,v\text{-path in }G\}$. A set $W\subset V$ is convex in G if $I(u,v) \subseteq W$ for every $u,v\in W$. A half-space is a convex set whose complement is convex. A graph $H=(V_1,E_1)$ is isometrically embeddable into a graph $G=(V_2,E_2)$ if and only if there exists an injection $\alpha$ from $V_1$ to $V_2$ such that for any $u,v\in V_1$, $d_H(u,v)=d_G(\alpha (u),\alpha (v))$. For any two adjacent vertices u and v in a graph G, let $W_{uv}$ = $\{x$: $d(x,u)<d(x,v)\}$, $W_{vu}$ = $\{x$: $d(x,v)<d(x,u)\}$ and $W_u^v$ = $\{x$: $d(x,u)=d(x,v)\}$. The set $W_{uv}$ is called the semicube of the graph G. Note that $W_{uv}$ is the set of vertices that are closer to u than to v. Eppstein [16] used the sets $W_{uv}$ and $W_{vu}$ as the key tool for efficient computation of the lattice dimension of graphs. We establish the desired characterizations of the two graphs: the partial cubes and partial Hamming graphs using the characterizations of these graphs in terms of the W-sets; namely $W_{uv}$, $W_{vu}$, and $W_u^v$. We observe that the W-sets can also be defined using the intervals in G and in Section 4, we do the same for convenience of the proof.

The paper is organized as follows. In Section 2, we quote the Mulder-Nebeský theorem and present the axioms used in our characterizations. We give the implications of the axioms for a transit function. In Section 3, we present the axiomatic characterization of partial cubes using its interval function and also present the characterization of the interval function of partial cubes in terms of an arbitrary transit function along with the independence of the axioms. In Section 4, we present similar characterizations and the independence of the axioms for partial Hamming graphs.

2 The axioms for the characterization

In this section, we introduce all the axioms required for our characterizations. Given a transit function R on a non-empty set V, the underlying graph $G_R$ of R is the graph with vertex set V, where distinct u and v in V are joined by an edge if and only if $|R(u,v)|=2$. Next, we quote the Mulder-Nebeský theorem below.

Theorem 1

(Mulder-Nebeský theorem).

[20] Let R from $V\times V\to 2^V$ be a function on V, with the underlying graph $G_R$, and let I be the interval function of $G_R$. The following statements are equivalent.

1. $R=I$

2. R satisfies axioms:

• $(t1)$ $x\in R(x,y)$ for all $x\in V$,

• $(t2)$ $R(x,y)=R(y,x),\text{ for all }x,y\in V$

• $(b2)$ If $x\in R(u,v)$ then $R(v,x)$ $\subseteq$ $R(u,v)$ for all u, v, x $\in V$

• $(c4)$ If $x\in R(u,v)$ then $R(u,x)\cap R(x,v)=\left\{x\right\}$ for all u, v, $x\in V$

• $(c5)$ If $x\in R(u,v)$ and $y\in R(x,u)$ then $x\in R(y,v)$ for all u, v, x, y $\in V$

• $(s1)$ If $R(u$,ū$)=\{u,$ū$\}$, $R(v$, $\overline{v}$ $)=\{v,$ $\overline{v}$ $\}$, $u\in R($ū, $\overline{v}$ $)$ and ū, $\overline{v}$ $\in R(u,v)$, then $v\in R($ū, $\overline{v}$ $)$ for all u, v, ū, $\overline{v}$ $\in V$.

• $(s2)$ If $R(u,$ū$)=\{u,$ū$\}$, $R(v,$ $\overline{v}$ $)=\{v,$ $\overline{v}$ $\}$, ū $\in R(u,v)$, $\overline{v}$ $\notin R(u,v)$, and $v\notin R($ū, $\overline{v}$ $)$, then ū $\in R(u,$ $\overline{v}$ $)$ for all u, ū, v, $\overline{v}$ $\in V$.

For bipartite graphs, a new axiom was introduced in [7] which is, $$(dp)R(x,y)=\{x,y\}\Rightarrow y\in R(x,z)orx\in R(y,z),\text{for all }x,y,z\in V$$

The theorem characterizing the interval function of bipartite graphs, presented in [7] is given below.

Theorem 2.

[7] The interval function I of a connected graph G satisfies $(bp)$ if and only if G is a bipartite graph.

We also need the following implications of axioms:

Lemma 1.

[7] Let R be a transit function satisfying axioms $(b1)$, $(b2)$, and $(bp)$ on V. Then R satisfies axioms $(s1)$ and $(s2)$.

Here the axiom $(b1)$ is,

1. $(b1)$ $x\in R(u,v)$, $x\ne v$ $\Rightarrow$ $v\notin R(u,x)$, for all $u,v,x\in V$

Lemma 2.

[3, 20] For a transit function R, $(c5)\Rightarrow (c4)\Rightarrow (b1)$.

From the work in [5], we derive the following four axioms which are going to be the essential characterizing axioms for the interval function of partial cubes and partial Hamming graphs.

For all u, v, x, y, z $\in V$;

$(ch)$ $R(u,v)=\{u,v\}$, $u\in R(x,v)$, $u\in R(y,v)$, and $z\in R(x,y)$ $\Rightarrow$ $u\in R(z,v)$.

$(cc)$ $R(u,v)=\{u,v\}$, $u\notin R(x,v)$, $u\notin R(y,v)$ and $z\in R(x,y)$ $\Rightarrow$ $u\notin R(z,v)$

$(\mathit{che})$ $R(u,v)=\{u,v\}$, $u\notin R(x,v)$, $v\notin R(x,u)$, $u\notin R(y,v)$, $v\notin R(y,u)$ and $z\in R(x,y)$ $\Rightarrow$ $u\notin R(z,v)$ and $v\notin R(z,u)$

$(\mathit{cce})$ $R(u,v)=\{u,v\}$ and [$u\in R(x,v)$ or $v\in R(x,u)$] and [$u\in R(y,v)$ or $v\in R(y,u)$] and $z\in R(x,y)$ $\Rightarrow$ $u\in R(z,v)$ or $v\in R(z,u)$

It is evident that, if a transit function R satisfies the axiom $(cc)$ then R satisfies the axiom $(ch)$. Moreover, we prove that if R satisfies the axioms $(b1)$, $(\mathit{cce})$ and $(cc)$ then it satisfies $(ch)$. The interval function of an arbitrary graph always satisfies the axiom $(b1)$.

Now, we prove the following lemma.

Lemma 3.

Let V be a nonempty set and R a transit function on V. Then the following holds.

1. If R satisfies the axiom $(cc)$, then R satisfies the axiom $(\mathit{che})$. That is, $(cc)\Rightarrow (\mathit{che}).$

2. If R satisfies the axioms $(b1)$, $(\mathit{cce})$ and $(cc)$ then R satisfies $(ch)$.

Proof.

The implication $(1)$ is straightforward.

$(2)$ Assume that R satisfies $(b1)$, $(\mathit{cce})$ and $(cc)$. For $u,v,x,y,z\in V$, let $R(u,v)=\{u,v\}$, $u\in R(x,v)$, $u\in R(y,v)$, $z\in R(x,y)$. Since $u\in R(x,v)$ and $u\ne v$, by (b1) we have $v\notin R(x,u)$. Similarly, since $u\in R(y,v)$ and $u\ne v$ we get $v\notin R(y,u)$. That is, $R(u,v)=\{u,v\}$, $v\notin R(x,u)$, $v\notin R(y,u)$ and $z\in R(x,y)$ and by (cc), we get $v\notin R(z,u)$. Now, since $R(u,v)=\{u,v\}$, $u\in R(x,v)$, $u\in R(y,v)$ and $z\in R(x,y)$, by $(\mathit{cce})$ we get either $u\in R(z,v)$ or $v\in R(z,u)$. But we already have $v\notin R(z,u)$. Then the only possibility is $u\in R(z,v)$. Hence $(ch)$ holds. ▪

Lemma 4.

Let R be a transit function satisfying axioms $(\mathit{cce})$ and $(c5)$ on V. Then R satisfies the axiom $(s1)$.

Proof.

First note that, since R is a transit function satisfying $(c5)$, by Lemma 2, R satisfies axiom $(b1)$. For any arbitrary u, $\overline{u}$, v, $\overline{v}\in V$, let $R(u,\overline{u})=\{u,\overline{u}\}$, $R(v,\overline{v})=\{v,\overline{v}\}$, $u\in R(\overline{u},\overline{v})$ and $\overline{u},\overline{v}$ $\in R(u,v)$. Since, $R(v,\overline{v})=\{v,\overline{v}\}$, $v\in R(v,\overline{v})$, $\overline{v}\in R(v,u)$, $\overline{u}\in R(u,v)$, by $(\mathit{cce})$, either $v\in R(\overline{u},\overline{v})$ or $\overline{v}\in R(v,\overline{u})$. Suppose, $\overline{v}\in R(v,\overline{u})$. Now, as $\overline{u}$ $\in R(u,v)$ and $\overline{v}\in R(v,\overline{u})$, by $(c5)$ we have, $\overline{u}\in R(u,\overline{v})$. This is a contradiction, since $u\in R(\overline{u},\overline{v})$, by $(b1)$ $\overline{u}\notin R(u,\overline{v})$. Thus R satisfies the axiom $(s1)$. ▪

3 Axiomatic characterization of interval function of partial cubes

In this section, we characterize the interval function of partial cubes by using the axioms $(ch)$ and $(bp)$ on an arbitrary transit function. The semicubes $W_{uv}$ and $W_{vu}$ are known as opposite semicubes. Clearly, two opposite semicubes are disjoint and they were used to characterize bipartite graphs as follows.

Theorem 3.

[23] A graph $G=(V,E)$ is bipartite if and only if the semicubes $W_{uv}$ and $W_{vu}$ form a partition of V for any edge $uv\in E$.

We also require the following characterization of partial cubes in terms of the convexity of the semicubes, due to Djoković in [14].

Theorem 4.

[14] G is a partial cube if and only if G is bipartite and for any edge uv, the semicubes $W_{uv}$ and $W_{vu}$ are convex.

Now, we have the following theorem on the characterization of interval function I of partial cubes.

Theorem 5.

The interval function I of a connected graph G satisfies axiom $(ch)$ and $(bp)$ if and only if G is a partial cube.

Proof.

Suppose G is a partial cube. Then by Theorem 4, G is bipartite and for any edge ab, $W_{ab}$ and $W_{ba}$ are convex. By Theorem 2, I satisfies $(bp)$. It is enough to show that I satisfies $(ch)$. For, consider arbitrary u, v, x, y, z such that $I(u,v)$ = $\{u,v\}$, $u\in I(x,v)$, $u\in I(y,v)$ and $z\in I(x,y)$. Since $u\in I(x,v)$, by definition, we have $d(x,u)+d(u,v)$ = $d(x,v)$ and we get $d(x,u)<d(x,v)$. So $x\in W_{uv}$. Similarly we get $y\in W_{uv}$. Since $z\in I(x,y)$ and since $W_{uv}$ is convex, we must have $z\in W_{uv}$. ie, $d(u,z)<d(v,z)$. And since $d(u,v)=1$, we get $d(u,z)+d(u,v)$ = $d(z,v)$. That is, $u\in I(z,v)$ and hence $(ch)$ holds.

Conversely, suppose I satisfies $(ch)$ and $(bp)$. Then by Theorem 2, G is bipartite. It is enough to show that $W_{uv}$ and $W_{vu}$ are convex. Since G is a bipartite graph, it is clear that $W_{uv}\cap W_{vu}$ = $\varphi$ and $W_{uv}\cup W_{vu}$ = V. Now let x, y $\in W_{vu}$ and $z\in I(x,y)$, for any arbitrary edge uv. Then $I(u,v)$ = $\{u,v\}$, $v\in I(x,u)$, $v\in I(y,u)$ and $z\in I(x,y)$. Then by $(ch)$, we have $v\in I(z,u)$. That is, $d(v,z)<d(z,u)$ which implies $z\in W_{vu}$. Therefore $W_{vu}$ is convex. Similarly, we get $W_{uv}$ is also convex. Hence the theorem. ▪

By Theorem 5 and using Lemmas 1, 2, and Theorem 1, we obtain the following theorem, which gives the axiomatic characterization of interval function of partial cubes by using a set of axioms defined on a function R.

Theorem 6.

Let $R:V\times V\to 2^V$ be any function on a finite set V and $G_R$ be the underlying graph of R. Then R satisfies axioms $(t1)$, $(t2)$, $(t3)$, $(c5)$, $(b2)$, $(bp)$ and $(ch)$ if and only if $G_R$ is a partial cube and $I_{G_R}=R$.

The following examples show that the axioms $(t1)$, $(t2)$, $(t3)$, $(c5)$, $(b2)$, $(bp)$ and $(ch)$ form an independent set of axioms.

Example 1.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(bp)$, $(ch)$ $\nRightarrow$ $(c5)$

Let $V=\{a,b,c,d,e\}$ and define R as follows, $R(a,b)=R(a,c)=R(b,c)=\{a,b,c\}$ and for any other distinct pair x, y $\in V$, $R(x,y)=V$. For every $x\in V$, $R(x,x)=\left\{x\right\}$, and $R(x,y)=R(y,x)$ for $x,y\in V$. It is easy to see that R is a transit function and R satisfies axioms $(b2)$, $(bp)$ and $(ch)$ on V, but does not satisfy $(c5)$, since $d\in R(e,b)$, $a\in R(e,d)$ and $d\notin R(a,b)$.

Example 2.

$(t1)$, $(t2)$, $(t3)$, $(c5)$, $(bp)$, $(ch)$ $\nRightarrow$ $(b2)$

Let $V=\{a,b,c,d,e\}$ and define R as follows, $R(a,b)=\{a,b,c,e\}$, $R(a,c)=\{a,c\}$, $R(a,d)=\{a,d,c\}$, $R(a,e)=\{a,e,c,d\}$, $R(c,d)=\{c,d\}$, $R(c,e)=\{c,e,d\}$, $R(c,b)=\{c,b,d,e\}$, $R(d,e)=\{d,e\}$, $R(d,b)=\{d,e,b\}$, $R(e,b)=\{e,b\}$ and for any $x\in V$, $R(x,x)=\left\{x\right\}$ and $R(x,y)=R(y,x)$ for x, $y\in V$. It is easy to see that R is a transit function and R satisfies axiom $(c5)$, $(bp)$ and $(ch)$ on V but does not satisfy $(b2)$, since $c\in R(a,b)$ and $R(c,b)⊈R(a,b)$.

Example 3.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(bp)$, $(c5)$ $\nRightarrow$ $(ch)$

Let $V=\{a,b,c,d,e\}$ and define R as follows, $R(a,b)=\{a,b,d,e\}$, $R(a,c)=\{a,c,d,e\}$, $R(b,c)=\{b,c,d,e\}$, $R(d,e)=\{a,b,c,d,e\}$ and $R(x,y)=\{x,y\}$ for any other distinct pair of vertices x and y $\in V$, and for any $x\in V$, $R(x,x)=\left\{x\right\}$ and $R(x,y)=R(y,x)$ for x, $y\in V$. It is clear that R is a transit function and R satisfies axiom $(bp)$, $(b2)$ and $(c5)$ on V, but does not satisfy axiom $(ch)$, since $R(e,a)=\{e,a\}$, $e\in R(b,a)$, $e\in R(c,a)$, $d\in R(b,c)$ and $e\notin R(d,a)$.

Example 4.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(ch)$ $\nRightarrow$ $(bp)$

Let $V=\{a,b,c\}$ and define R as follows, $R(a,b)=\{a,b\}$, $R(b,c)=\{b,c\}$, $R(a,c)=\{a,c\}$ and for any $x\in V$, $R(x,x)=\left\{x\right\}$ and $R(x,y)=R(y,x)$ for $x,y\in V$. It is clear that R is a transit function and R satisfies axioms $(ch)$, $(c5)$ and $(b2)$, but does not satisfy axiom $(bp)$, since $R(a,b)=\{a,b\}$ and $a\notin R(b,c)$ and $b\notin R(a,c)$.

Example 5.

$(t2)$, $(t3)$, $(b2)$, $(c5)$, $(ch)$, $(bp)$ $\nRightarrow$ $(t1)$

Let $V=\{a,b,c\}$ and define R as follows, $R(a,b)=\left\{a\right\}=R(b,a)$, $R(a,c)=\left\{a\right\}=R(c,a)$, $R(c,b)=\left\{c\right\}=R(b,c)$. Here R does not satisfy $(t1)$ but it holds all other axioms trivially.

Example 6.

$(t1)$, $(t3)$, $(b2)$, $(c5)$, $(ch)$, $(bp)$ $\nRightarrow$ $(t2)$

Let $V=\{a,b,c,d\}$ and define R as follows, $R(a,c)=\{a,c,b\}$, $R(a,d)=\{a,b,c,d\}$, $R(b,d)=\{b,c,d\}$, $R(b,a)=\{b,c,d,a\}$, $R(c,a)=\{c,d,a\}$, $R(c,b)=\{c,d,a,b\}$, $R(d,b)=\{d,a,b\}$, $R(d,c)=\{d,a,b,c\}$ and for any other distinct pair x, y $\in V$, $R(x,y)=\{x,y\}$ and $R(x,x)=\left\{x\right\}$, for every $x\in V$. Clearly, R does not satisfies $(t2)$ but it satisfies $(t1)$, $(t3)$, $(b2)$, $(c5)$, $(ch)$ and $(bp)$.

Example 7.

$(t2)$, $(t1)$, $(b2)$, $(c5)$, $(ch)$, $(bp)$ $\nRightarrow$ $(t3)$

Let $V=\{a,b,c,d\}$ and define R as $R(u,v)=V$ for all u, v in V. Clearly, R does not satisfies $(t3)$ but it satisfies $(t1)$, $(t2)$, $(b2)$, $(c5)$, $(ch)$ and $(bp)$.

4 Axiomatic characterization of interval function of partial Hamming graphs

We first define the W-sets in terms of the intervals in G. That is, $W_{uv}$ = $\{x:u\in I(x,v)\}$, $W_{vu}$ = $\{x:v\in I(x,u)\}$, $W_u^v$ $=\{x:u\notin I(x,v)$ and $v\notin I(x,u)$}. The W-sets are used to characterize the partial Hamming graphs. Clearly, in the case of partial cubes, the sets $W_{uv}$ and $W_{vu}$ partition the vertex set V of the graph. But, for the case of non-bipartite Hamming graphs, the three sets $W_{uv}$, $W_{vu}$, and $W_u^v$ form a partition of V.

We quote the following characterization of partial Hamming graphs due to Chepoi in [12].

Theorem 7.

[12] A graph G is a partial Hamming graph if and only if for every edge uv, the sets, $W_{uv}$, $W_{vu}$, $W_u^v$ arehalf-spaces.

Now, we have the main theorem.

Theorem 8.

The interval function I of a connected graph G satisfies axioms $(b1)$, $(cc)$, and $(\mathit{cce})$ if and only if G is a partial Hamming graph.

Proof.

Suppose G is a partial Hamming graph. Then by Theorem 7, $W_{uv}$, $W_{vu}$, $W_u^v$ are half-spaces. Clearly the interval function I of G satisfies axiom $(b1)$. To prove $(cc)$ holds: for any u, v, x, y, z, suppose $I(u,v)=\{u,v\}$, $u\notin I(x,v)$, $u\notin I(y,v)$, $z\in I(x,y)$. Then by definition of $W_{uv}$ we get $x,y\in \overline{W_{uv}}$. Since $\overline{W_{uv}}$ is convex we get $z\in \overline{W_{uv}}$. That is, $u\notin I(z,v)$.

To prove $(\mathit{cce})$ holds: for any u, v, x, y, z suppose $I(u,v)=\{u,v\}$ and ($u\in I(x,v)$ or $v\in I(x,u)$) and ($u\in I(y,v)$ or $v\in I(y,u)$) and $z\in I(x,y)$. Here since I satisfies $(b1)$, the possibilities are $(1)$ $u\in I(x,v)$ and $u\in I(y,v)$, $(2)$ $v\in I(x,u)$ and $v\in I(y,u)$, $(3)$ $u\in I(x,v)$ and $v\in I(y,u)$, or $(4)$ $v\in I(x,u)$ and $u\in I(y,v)$.

If $(1)$ holds then $x,y\in W_{uv}$, and since $W_{uv}$ is convex we get $z\in W_{uv}$ and hence $u\in I(z,v)$. If $(2)$ holds then $x,y\in W_{vu}$, and since $W_{vu}$ is convex we get $z\in W_{vu}$ and hence $v\in I(z,u)$. Similarly, in the remaining two cases, both x and y lies in $\overline{W_u^v}$ and since G is a partial Hamming graph $\overline{W_u^v}$ is convex and $z\in \overline{W_u^v}$, hence by definition of $W_u^v$, $u\in I(z,v)$ or $v\in I(z,u)$.

Conversely, suppose that I satisfies $(cc)$ and $(\mathit{cce})$. Clearly $(cc)$ $\Rightarrow$ $(\mathit{che})$, and by Lemma 3, I satisfies $(ch)$. We have to show that G is a partial hamming graph. By Theorem 7, it is enough to show that for any edge uv, the sets $W_{uv}$, $W_{vu}$, $W_u^v$ are half-spaces. Let uv be any edge. To show that $W_{uv}$ is a half-space, we have to show that $W_{uv}$ and its complement $\overline{W_{uv}}$ are convex.

To show that $W_{uv}$ is convex : we will prove that, if $x,y\in W_{uv}$ then $I(x,y)\subseteq W_{uv}$. For, let $x,y\in W_{uv}$ and $z\in I(x,y)$. By definition of $W_{uv}$, we have $u\in I(x,v)$ and $u\in I(y,v)$. So, by axiom $(ch)$ we get $u\in I(z,v)$. This implies $z\in W_{uv}$, by the definition of $W_{uv}$.

To show that $\overline{W_{uv}}$ is convex: we will prove that, if $x,y\in \overline{W_{uv}}$ then $I(x,y)\subseteq \overline{W_{uv}}$. For, let $x,y\in \overline{W_{uv}}$ and $z\in I(x,y)$. By definition of $W_{uv}$, we have $u\notin I(x,v)$ and $u\notin I(y,v)$. So, by axiom $(cc)$ we get $u\notin I(z,v)$. This implies $z\notin W_{uv}$, that is, $z\in \overline{W_{uv}}$.

Similarly we can show that $W_{vu}$ is a half-space. Now it is enough to show that $W_u^v$ is a half-space.

To show that $W_u^v$ is convex : we will prove that, if $x,y\in W_u^v$ then $I(x,y)\subseteq W_u^v$. For, let $x,y\in W_u^v$ and $z\in I(x,y)$. Since $x\in W_u^v$, by definition of $W_u^v$, we have $u\notin I(x,v)$ and $v\notin I(x,u)$. Also since $y\in W_u^v$, we have $u\notin I(y,v)$ and $v\notin I(y,u)$. So, by axiom $(\mathit{che})$ we get $u\notin I(z,v)$ and $v\notin I(z,u)$. Thatis $z\in W_u^v$.

To show that $\overline{W_u^v}$ is convex : Let $x,y\in \overline{W_u^v}$ and $z\in I(x,y)$. Since $x\in \overline{W_u^v}$, by definition of $W_u^v$, we have either $u\in I(x,v)$ or $v\in I(x,u)$. Also, since $y\in W_u^v$, we have either $u\in I(y,v)$ or $v\in I(y,u)$. Hence, by axiom $(\mathit{cce})$ we get $u\in I(z,v)$ or $v\in I(z,u)$. So $z\notin W_u^v$. That is $I(x,y)\subseteq \overline{W_u^v}$. This completes theproof. ▪

By Theorem 8 and using Lemmas 1, 2, 4, and Theorem 1, we can conclude the following theorem, which gives the axiomatic characterization of interval function of partial Hamming graphs by using an independent set of axioms defined on a function R.

Theorem 9.

Let $R:V\times V\to 2^V$ be any function on a finite set V and $G_R$ be the underlying graph of R. Then R satisfies axioms $(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(s2)$, $(cc)$ and $(\mathit{cce})$ if and only if $G_R$ is a partial Hamming graph and $I_{G_R}=R$.

The following examples show that the axioms $(t1)$, $(t2)$, $(t3)$, $(b2)$, $(s2)$, $(\mathit{cce})$, $(cc)$, and $(c5)$ form an independent set of axioms.

Example 8.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(s2)$, $(\mathit{cce})$, $(cc)$ $\nRightarrow$ $(c5)$. See Example 1

Example 9.

$(t1)$, $(t2)$, $(t3)$, $(c5)$, $(s2)$, $(\mathit{cce})$, $(cc)$ $\nRightarrow$ $(b2)$. See Example 2

Example 10.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(s2)$, $(cc)$ $\nRightarrow$ $(\mathit{cce})$

Let $V=\{a,b,c,d,e\}$. Let R be the interval function I of a 5 cycle (namely abcdea). It is easy to see that R satisfies axioms $(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(s2)$ and $(cc)$. But R doesn’t satisfy $(\mathit{cce})$ because, $R(a,b)=\{a,b\}$, $a\in R(e,b)$, $b\in R(c,a)$, $d\in R(c,e)$ but $a\notin R(d,b)$ and $b\notin R(d,a)$.

Example 11.

$(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(s2)$, $(\mathit{cce})$ $\nRightarrow$ $(cc)$

Let $V=\{a,b,c,d,e\}$ and define R as follows: $R(a,c)=\{a,c,b,d\}$, $R(a,e)=\{a,e,b,d\}$, $R(b,d)=\{a,b,d,c,e\}$, $R(e,c)=\{e,c,b,d\}$ and $R(u,v)=\{u,v\}$ for any pair of vertices $u,v\in V$ and for any $u\in V$, $R(u,u)=\left\{u\right\}$. It is easy to see that R satisfies axioms $(t1)$, $(t2)$, $(t3)$, $(b2)$, $(c5)$, $(s2)$ and $(\mathit{cce})$. But R doesn’t satisfy $(cc)$, since $R(a,b)=\{a,b\}$, $a\notin R(e,b)$, $a\notin R(b,c)$, $d\in R(e,c)$ but $a\in R(d,b)$.

Example 12.

$(t1)$, $(t2)$, $(t3)$, $(c5)$, $(b2)$, $(\mathit{cce})$, $(cc)$ $\nRightarrow$ $(s2)$

Let $V=\{a,b,c,d\}$ and define R as follows, $R(a,b)=\{a,b\}$, $R(a,c)=\{a,c,b\}$, $R(a,d)=\{a,d\}$, $R(c,d)=\{c,d\}$, $R(c,b)=\{c,b\}$, $R(d,b)=\{d,a,b\}$, and for any $x\in V$, $R(x,x)=\left\{x\right\}$ and $R(x,y)=R(y,x)$ for x, $y\in V$. It is easy to see that R satisfies axioms $(t1)$, $(t2)$, $(t3)$, $(c5)$, $(b2)$, $(\mathit{cce})$ and $(cc)$ on V but does not satisfy $(s2)$, since $R(a,b)=\{a,b\}$, $R(c,d)=\{c,d\}$, $b\in R(a,c)$, $d\notin R(a,c)$, $c\notin R(b,d)$ but $b\notin R(a,d)$

Example 13.

$(t2)$, $(t3)$, $(c5)$, $(b2)$, $(\mathit{cce})$, $(cc)$, $(s2)$ $\nRightarrow$ $(t1)$. See Example 5.

Example 14.

$(t1)$, $(t3)$, $(c5)$, $(b2)$, $(\mathit{cce})$, $(cc)$, $(s2)$ $\nRightarrow$ $(t2)$. See Example 6.

Example 15.

$(t1)$, $(t2)$, $(c5)$, $(b2)$, $(\mathit{cce})$, $(cc)$, $(s2)$ $\nRightarrow$ $(t3)$. See Example 7.

Additional information

Funding

M.C. acknowledges the financial support from SERB, Department of Science & Technology, Govt. of India (research project under MATRICS scheme No. MTR/2017/000238). J.J acknowledges the financial support from University of Kerala, India, for providing University JRF (No: 445/2020/UOK, 391/2021/UOK, 3093/2022/ UOK, 4202/2023/UOK). L.K acknowledges the financial support from CSIR, Government of India for providing CSIR Senior Research Fellowship (CSIR-SRF) (No: 09/102(0260)/2019-EMR-I).