![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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.
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 ’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 [Citation27] and later, Chepoi [Citation12] and Wilkiet [Citation26] proved several characterizations of these graphs. In [Citation27], it is proved that any two isometric embedding of a graph into a Hamming graph are equivalent. Using this result, a simple algorithm, called Winkler’s algorithm, for recognizing partial Hamming graphs was also presented. Later, Wilkeit [Citation26] gave an
recognition algorithm and in 1993 Imrich and Klavžar [Citation18] and in 1994 Aurenhammer [Citation1] gave an
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, [Citation26].
The partial cubes, also known as binary partial Hamming graphs are the bipartite partial Hamming graphs. Partial cubes were introduced by Graham and Pollak [Citation17] and these graphs finds several applications in chemical graph theory [Citation13]. Partial cubes were first characterized by Djoković in 1973 [Citation14]. Further, Avis [Citation2], Winkler [Citation27], Roth and Winkler [Citation24], Chepoi [Citation10, Citation11] and Ovchinnikov [Citation23] gave different characterizations. In [Citation23], 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 , median graphs, netlike partial cubes and trees [Citation25]. Another class of partial cubes extending median graphs is the class of ample graphs [Citation4]. An
time algorithm for the recognition of partial cubes is established in [Citation18], while [Citation15] presents an
timealgorithm.
Recently, Chalopin et al. [Citation5] 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 [Citation5] 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 , which holds exactly when P holds and the problem is solved by finding such a sentence
. 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 [Citation5].
In the approach initiated by Nebeský, Mulder, Sholander, Changat, etc. [Citation6, Citation20, Citation21], 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 ) 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 [Citation5] 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 [Citation19]. Given a non-empty set V, a transit function is defined as a function satisfying the following three axioms:
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 [Citation22]. 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 [Citation21]. 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 [Citation20] (this is known as the Mulder-Nebeský theorem). Further, the study is extended to disconnected graph by Changat et al. [Citation6].
Moreover, axiomatic characterization of the interval function of trees, block graphs, median graphs, modular graphs and geodetic graphs were studied, see [Citation8] and [Citation3]. Similar characterizations of the interval function of claw and paw-free graphs, bipartite graphs and forests have been obtained in [Citation7, Citation9]. 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 . More often, we may use the notation G for such a graph. We denote the standard shortest path metric in G by
(or d if the graph G is evident).
The interval function denoted as I of a graph G is defined as the function with
. A set
is convex in G if
for every
. A half-space is a convex set whose complement is convex. A graph
is isometrically embeddable into a graph
if and only if there exists an injection
from
to
such that for any
,
. For any two adjacent vertices u and v in a graph G, let
=
:
,
=
:
and
=
:
. The set
is called the semicube of the graph G. Note that
is the set of vertices that are closer to u than to v. Eppstein [Citation16] used the sets
and
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
,
, and
. 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 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
. Next, we quote the Mulder-Nebeský theorem below.
Theorem 1
(Mulder-Nebeský theorem).
[Citation20] Let R from be a function on V, with the underlying graph
, and let I be the interval function of
. The following statements are equivalent.
R satisfies axioms:
for all
,
If
then
for all u, v, x
If
then
for all u, v,
If
and
then
for all u, v, x, y
If
,ū
ū
,
,
,
ū,
and ū,
, then
ū,
for all u, v, ū,
.
If
ū
ū
,
, ū
,
, and
ū,
, then ū
for all u, ū, v,
.
For bipartite graphs, a new axiom was introduced in [Citation7] which is,
The theorem characterizing the interval function of bipartite graphs, presented in [Citation7] is given below.
Theorem 2.
[Citation7] The interval function I of a connected graph G satisfies if and only if G is a bipartite graph.
We also need the following implications of axioms:
Lemma 1.
[Citation7] Let R be a transit function satisfying axioms ,
, and
on V. Then R satisfies axioms
and
.
Here the axiom is,
1.
,
, for all
Lemma 2.
[Citation3, Citation20] For a transit function R, .
From the work in [Citation5], 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 ;
,
,
, and
.
,
,
and
,
,
,
,
and
and
and [
or
] and [
or
] and
or
It is evident that, if a transit function R satisfies the axiom then R satisfies the axiom
. Moreover, we prove that if R satisfies the axioms
,
and
then it satisfies
. The interval function of an arbitrary graph always satisfies the axiom
.
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.
If R satisfies the axiom
, then R satisfies the axiom
. That is,
If R satisfies the axioms
,
and
then R satisfies
.
Proof.
The implication is straightforward.
Assume that R satisfies
,
and
. For
, let
,
,
,
. Since
and
, by (b1) we have
. Similarly, since
and
we get
. That is,
,
,
and
and by (cc), we get
. Now, since
,
,
and
, by
we get either
or
. But we already have
. Then the only possibility is
. Hence
holds. ▪
Lemma 4.
Let R be a transit function satisfying axioms and
on V. Then R satisfies the axiom
.
Proof.
First note that, since R is a transit function satisfying , by Lemma 2, R satisfies axiom
. For any arbitrary u,
, v,
, let
,
,
and
. Since,
,
,
,
, by
, either
or
. Suppose,
. Now, as
and
, by
we have,
. This is a contradiction, since
, by
. Thus R satisfies the axiom
. ▪
3 Axiomatic characterization of interval function of partial cubes
In this section, we characterize the interval function of partial cubes by using the axioms and
on an arbitrary transit function. The semicubes
and
are known as opposite semicubes. Clearly, two opposite semicubes are disjoint and they were used to characterize bipartite graphs as follows.
Theorem 3.
[Citation23] A graph is bipartite if and only if the semicubes
and
form a partition of V for any edge
.
We also require the following characterization of partial cubes in terms of the convexity of the semicubes, due to Djoković in [Citation14].
Theorem 4.
[Citation14] G is a partial cube if and only if G is bipartite and for any edge uv, the semicubes and
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 and
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, and
are convex. By Theorem 2, I satisfies
. It is enough to show that I satisfies
. For, consider arbitrary u, v, x, y, z such that
=
,
,
and
. Since
, by definition, we have
=
and we get
. So
. Similarly we get
. Since
and since
is convex, we must have
. ie,
. And since
, we get
=
. That is,
and hence
holds.
Conversely, suppose I satisfies and
. Then by Theorem 2, G is bipartite. It is enough to show that
and
are convex. Since G is a bipartite graph, it is clear that
=
and
= V. Now let x, y
and
, for any arbitrary edge uv. Then
=
,
,
and
. Then by
, we have
. That is,
which implies
. Therefore
is convex. Similarly, we get
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 be any function on a finite set V and
be the underlying graph of R. Then R satisfies axioms
,
,
,
,
,
and
if and only if
is a partial cube and
.
The following examples show that the axioms ,
,
,
,
,
and
form an independent set of axioms.
Example 1.
,
,
,
,
,
Let and define R as follows,
and for any other distinct pair x, y
,
. For every
,
, and
for
. It is easy to see that R is a transit function and R satisfies axioms
,
and
on V, but does not satisfy
, since
,
and
.
Example 2.
,
,
,
,
,
Let and define R as follows,
,
,
,
,
,
,
,
,
,
and for any
,
and
for x,
. It is easy to see that R is a transit function and R satisfies axiom
,
and
on V but does not satisfy
, since
and
.
Example 3.
,
,
,
,
,
Let and define R as follows,
,
,
,
and
for any other distinct pair of vertices x and y
, and for any
,
and
for x,
. It is clear that R is a transit function and R satisfies axiom
,
and
on V, but does not satisfy axiom
, since
,
,
,
and
.
Example 4.
,
,
,
,
,
Let and define R as follows,
,
,
and for any
,
and
for
. It is clear that R is a transit function and R satisfies axioms
,
and
, but does not satisfy axiom
, since
and
and
.
Example 5.
,
,
,
,
,
Let and define R as follows,
,
,
. Here R does not satisfy
but it holds all other axioms trivially.
Example 6.
,
,
,
,
,
Let and define R as follows,
,
,
,
,
,
,
,
and for any other distinct pair x, y
,
and
, for every
. Clearly, R does not satisfies
but it satisfies
,
,
,
,
and
.
Example 7.
,
,
,
,
,
Let and define R as
for all u, v in V. Clearly, R does not satisfies
but it satisfies
,
,
,
,
and
.
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, =
,
=
,
and
}. The W-sets are used to characterize the partial Hamming graphs. Clearly, in the case of partial cubes, the sets
and
partition the vertex set V of the graph. But, for the case of non-bipartite Hamming graphs, the three sets
,
, and
form a partition of V.
We quote the following characterization of partial Hamming graphs due to Chepoi in [Citation12].
Theorem 7.
[Citation12] A graph G is a partial Hamming graph if and only if for every edge uv, the sets, ,
,
arehalf-spaces.
Now, we have the main theorem.
Theorem 8.
The interval function I of a connected graph G satisfies axioms ,
, and
if and only if G is a partial Hamming graph.
Proof.
Suppose G is a partial Hamming graph. Then by Theorem 7, ,
,
are half-spaces. Clearly the interval function I of G satisfies axiom
. To prove
holds: for any u, v, x, y, z, suppose
,
,
,
. Then by definition of
we get
. Since
is convex we get
. That is,
.
To prove holds: for any u, v, x, y, z suppose
and (
or
) and (
or
) and
. Here since I satisfies
, the possibilities are
and
,
and
,
and
, or
and
.
If holds then
, and since
is convex we get
and hence
. If
holds then
, and since
is convex we get
and hence
. Similarly, in the remaining two cases, both x and y lies in
and since G is a partial Hamming graph
is convex and
, hence by definition of
,
or
.
Conversely, suppose that I satisfies and
. Clearly
, and by Lemma 3, I satisfies
. 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
,
,
are half-spaces. Let uv be any edge. To show that
is a half-space, we have to show that
and its complement
are convex.
To show that is convex : we will prove that, if
then
. For, let
and
. By definition of
, we have
and
. So, by axiom
we get
. This implies
, by the definition of
.
To show that is convex: we will prove that, if
then
. For, let
and
. By definition of
, we have
and
. So, by axiom
we get
. This implies
, that is,
.
Similarly we can show that is a half-space. Now it is enough to show that
is a half-space.
To show that is convex : we will prove that, if
then
. For, let
and
. Since
, by definition of
, we have
and
. Also since
, we have
and
. So, by axiom
we get
and
. Thatis
.
To show that is convex : Let
and
. Since
, by definition of
, we have either
or
. Also, since
, we have either
or
. Hence, by axiom
we get
or
. So
. That is
. 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 be any function on a finite set V and
be the underlying graph of R. Then R satisfies axioms
,
,
,
,
,
,
and
if and only if
is a partial Hamming graph and
.
The following examples show that the axioms ,
,
,
,
,
,
, and
form an independent set of axioms.
Example 8.
,
,
,
,
,
,
. See Example 1
Example 9.
,
,
,
,
,
,
. See Example 2
Example 10.
,
,
,
,
,
,
Let . Let R be the interval function I of a 5 cycle (namely abcdea). It is easy to see that R satisfies axioms
,
,
,
,
,
and
. But R doesn’t satisfy
because,
,
,
,
but
and
.
Example 11.
,
,
,
,
,
,
Let and define R as follows:
,
,
,
and
for any pair of vertices
and for any
,
. It is easy to see that R satisfies axioms
,
,
,
,
,
and
. But R doesn’t satisfy
, since
,
,
,
but
.
Example 12.
,
,
,
,
,
,
Let and define R as follows,
,
,
,
,
,
, and for any
,
and
for x,
. It is easy to see that R satisfies axioms
,
,
,
,
,
and
on V but does not satisfy
, since
,
,
,
,
but
Example 13.
,
,
,
,
,
,
. See Example 5.
Example 14.
,
,
,
,
,
,
. See Example 6.
Example 15.
,
,
,
,
,
,
. See Example 7.
Additional information
Funding
References
- Aurenhammer, F., Formann, M., Idury, R. M., Schäffer, A. A, Wagner, F. (1994). Faster isometric embedding in products of complete graphs. Discrete Appl. Math 52(1): 17–28.
- Avis, D. (1981). Hypermetric spaces and the Hamming cone. Can. j. Math. 33(4): 795–802.
- Balakrishnan, K., Changat, M., Lakshmikuttyamma, A. K., Mathew, J., Mulder, H. M., Narasimha-Shenoi, P. G, Narayanan, N. (2015). Axiomatic characterization of the interval function of a block graph. Discrete Math 338(6): 885–894.
- Bandelt, H.-J., Chepoi, V., Dress, A, Koolen, J. (2006). Combinatorics of lopsided sets. Eur. J. Comb 27(5): 669–689.
- Chalopin, J., Changat, M., Chepoi, V, Jacob, J. (2022). First-order logic axiomatization of metric graph theory, arXiv preprint arXiv:2203.01070.
- Changat, M., Nezhad, F. H., Mulder, H. M, Narayanan, N. (2018). A note on the interval function of a disconnected graph. Discuss. Math. Graph Theory 38(1): 39–48.
- Changat, M., Nezhad, F. H, Narayanan, N. (2020). Axiomatic characterization of the interval function of a bipartite graph. Discrete Appl. Math 286: 19–28.
- Changat, M., Narasimha-Shenoi, P. G, Seethakuttyamma, G. (2019). Betweenness in graphs: A short survey on shortest and induced path betweenness. AKCE Int J Graphs Comb 16(1): 90–109.
- Changat, M., Nezhad, F. H, Narayanan, N. (2020). Interval function, induced path function,(claw, paw)-free graphs and axiomatic characterizations. Discrete Appl. Math 280: 53–62.
- Chepoi, V. (1988). Isometric subgraphs of Hamming graphs and d-convexity. Cybern. Syst. Anal. 24(1): 6–11.
- Chepoi, V. (1994). Separation of two convex sets in convexity structures. J. Geom. 50(1-2): 30–51.
- Chepoi, V. (1988). Isometric subgraphs of Hamming graphs and d-convexity. Cybern. Syst. Anal. 24(1): 6–11.
- Chepoi, V, Klavžar, S. (1997). The Wiener index and the Szeged index of benzenoid systems in linear time. J. Chem. Inf. Comput. Sci. 37(4): 752–755.
- Djoković, D. Ž. (1973). Distance–preserving subgraphs of hypercubes. J. Comb. Th. Ser. B 14(3): 263–267.
- Eppstein, D. (2011). Recognizing partial cubes in quadratic time. Jgaa. 15(2): 269–293.
- Eppstein, D. (2005). The lattice dimension of a graph. Eur. J. Comb 26(5): 585–592.
- Graham, R. L, Pollak, H. O. (1971). On the addressing problem for loop switching. The Bell Syst. Tech. J 50(88): 2495–2519.
- Imrich, W, Klavžar, S. (1993). A simple O(mn) algorithm for recognizing Hamming graphs. Bull. Inst. Comb. Appl 9: 45–56.
- Mulder, H. M. (2008). Transit functions on graphs (and posets)In: Changat, M., Klavžar, S., Mulder, H. M., Vijayakumar, A., eds. Convexity in Discrete Structures. Lecture Notes Series. Mysore: Ramanujan Math. Soc. pp. 117–130.
- Mulder, H. M, Nebeský, L. (2009). Axiomatic characterization of the interval function of a graph. Eur. J. Comb 30(5): 1172–1185.
- Mulder, H. M. (1980). The Interval Function of a Graph. MC Tracts.
- Sheela, L. K., Changat, M, Peterin, I. (2023). Axiomatic characterization of the Toll Walk Function of some graph classes. In: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings, pp. 427–446.
- Ovchinnikov, S. (2008). Partial cubes: structures, characterizations, and constructions. Discrete Math 308(23): 5597–5621.
- Roth, R. I, Winkler, P. M. (1986). Collapse of the metric hierarchy for bipartite graphs. Eur. J. Comb 7(4): 371–375.
- Polat, N. (2007). Netlike partial cubes I. General properties. Discr. Math 307(22): 2704–2722.
- Wilkeit, E. (1990). Isometric embeddings in Hamming graphs. J. Combin. Theory, Series B 50(2): 179–197.
- Winkler, P. M. (1984). Isometric embedding in product of complete graphs. Discrete Appl. Math 7(2): 221–225.