Electronic Journal of Graph Theory and Applications 12 .
, 147Ae156 A note on lower bounds for boxicity of graphs Akira Kamibeppu Department of Creative Engineering.
National Institute of Technology (KOSEN).
Kushiro College.
Kushiro.
Hokkaido 084-0916.
Japan.
kamibeppu@kushiro.
kosen-ac.
Abstract The boxicity of a graph G is the minimum non-negative integer k such that G is isomorphic to the intersection graph of a family of boxes in Euclidean k-space, where a box in Euclidean k-space is the Cartesian product of k closed intervals on the real line.
In this short note, we deAne the fractional boxicity of a graph as the optimum value of the linear relaxation of a covering problem with respect to boxicity, which gives a lower bound for its boxicity.
We show that the fractional boxicity of a graph is at least the lower bounds for boxicity given by Adiga et al.
We also present a natural lower bound for fractional boxicity of graphs.
The aim of this note is to discuss and focus on AuaccuracyAy rather than AusimplicityAy of these lower bounds for boxicity as the next step in the work by Adiga et al.
Keywords: hypergraph.
interval graph.
integer/linear program Mathematics Subject ClassiAcation : 05C62, 05C65, 05C72 DOI: 10.
5614/ejgta.
Introduction and Preliminaries A box in Euclidean k-space is the Cartesian product of k closed intervals on the real line.
The intersection graph of a family F of boxes in Euclidean k-space is the graph with F as the vertex set, where two boxes .
in F are adjacent if and only if they have non-empty intersection in the space.
The boxicity of a graph G, denoted by box(G), is the minimum non-negative integer k such that G is isomorphic to the intersection graph of a family of boxes in Euclidean k-space.
For example, a complete graph Kn with n vertices, a path Pn with n vertices, and a cycle Received: 15 November 2021.
Revised: 12 March 2024.
Accepted: 31 March 2024.
A note on lower bounds for boxicity of graphs Kamibeppu Cn with n vertices for n Ou 4 can be represented by the intersection graph of a family of boxes in 0-dimensional, 1-dimensional, and 2-dimensional space respectively .
n fact, box(Kn ) = 0, box(Pn ) = 1, box(Cn ) = .
The concept of boxicity of graphs was introduced by Roberts .
It has applications to measure the structural complexity of ecological and social networks .
, .
for detai.
So far many researchers have attempted to calculate or bound boxicity of graphs with speciAc structure.
Roberts .
found that the boxicity of a complete k-partite graph is equal to k, where the cardinality of each partite set is at least 2.
Roberts also proved that the maximum boxicity of graphs with n vertices is UO n2 UU .
lso see .
), where UOxUU denotes the largest integer at most x.
Cozzens .
found that the task of computing boxicity of graphs is NP-hard.
Chandran and Sivadasan .
presented upper bounds for chordal graphs, circular arc graphs.
AT-free graphs, co-comparability graphs, and permutation graphs by relating boxicity to treewidth.
Cozzens and Roberts .
obtained an upper bound for boxicity of split graphs, which contributed to relating boxicity to the cardinality of minimum vertex cover and the chromatic number in .
Relationships between boxicity and (Eule.
genus were found by Esperet and Joret in .
, 10, .
, which originated from researches of the boxicity of outerplanar graphs and planar graphs observed, respectively, by Scheinerman .
and Thomassen .
In addition, boxicity has notable topics related to the following .
invariants: maximum degree .
, .
and poset dimension .
, 12, .
In this short note we focus on lower bounds for boxicity of graphs.
Adiga et al.
presented a lower bound for the boxicity of a graph as in Lemma 1.
1 below, which also gives some lower bounds under various conditions on graphs.
Those lower bounds for boxicity in addition to the lower bound in Lemma 1.
2 are relatively easy to estimate by examination, but there is an example of a graph whose boxicity cannot be determined by those lower bounds .
ee Example 2.
4 and Remark 2.
In what follows, the symbol G denotes the complement of a graph G and the cardinality of a set X is denoted by |X|.
The symbol UOxUO denotes the smallest integer at least x.
Interval graphs are graphs of boxicity at most 1.
Lemma 1.
1 (.
Lemma 3.
The inequality box(G) Ou |E(G)|/|E(Imin )| holds for a noncomplete graph G, where Imin is an interval supergraph of G with V (Imin ) = V (G) and with the minimum number of edges among all such interval supergraphs of G.
Lemma 1.
2 (.
Lemma .
Let G be a graph.
Let S1 = .
1 , u2 , .
, un } and S2 = .
1 , v2 , .
, vn } be disjoint subsets of V (G) such that the only edges between S1 and S2 in G are the edges ui vi , where i OO .
, 2, .
, .
Then box(G) Ou UOn/2UO holds.
The next step in the work by Adiga et al.
is to discuss and focus on AuaccuracyAy rather than AusimplicityAy of these lower bounds for boxicity.
The purpose of this note is A to review the lower bound in Lemma 1.
1 for boxicity in the context of fractional graph theory.
A to introduce a fractional analogue of boxicity that will become a lower bound for boxicity.
A to present a natural lower bound for our fractional analogue of boxicity, which works on calculation of boxicity of some graphs better than Lemmas 1.
1 and 1.
A note on lower bounds for boxicity of graphs Kamibeppu In this note, all graphs are Anite, simple and undirected.
We use V (G) for the vertex set of a graph G and E(G) for the edge set of the graph G.
These notations are also used for hypergraphs.
A few concepts and results about .
graphs are needed to present a fractional analogue of A graph is said to be cointerval if its complement is an interval graph.
A cointerval edge covering of a graph G is a family C of cointerval subgraphs of G such that each edge of G is in some graph in C.
The following is a basic result on boxicity.
Theorem 1.
3 (.
Theorem .
Let G be a graph.
Then, box(G) O k if and only if there exists a cointerval edge covering C of G with |C| = k.
Hence box(G) = min{ |C| : C is a cointerval edge covering of G }.
Main Results In what follows, for n-dimensional vectors u and v, we write u Ou v to mean that each coordinate of u is at least the corresponding coordinate of v.
Let C be a family of hyperedges of a hypergraph H and we write C = {X1 , .
Xk }.
The family C is a covering of H if V (H) OI X1 OA A AOXk Our key idea for the deAnition of a fractional analogue of boxicity is in the way to deAne a hypergraph associated with a graph.
For a graph G, we deAne the hypergraph HG as follows:
V (HG ) = E(G) and E(HG ) = {E OC E(G) : E corresponds to a cointerval subgraph of G }.
Note that a covering of HG corresponds to a cointerval edge covering of G.
Hence the covering number of the hypergraph HG , the minimum cardinality of a covering of HG , is equal to the boxicity of G by Theorem 1.
For a graph G, let ei be an edge of G and Ej a hyperedge of HG .
Moreover, let MG be the incidence matrix of HG whose rows are indexed by all edges of G and whose columns are indexed by all cointerval subgraphs of G, that is, the i, j-entry of MG is equal to 1 if ei OO Ej , and otherwise 0.
Write E(HG ) = {E1 , .
En }.
Let C be a family of hyperedges in E(HG ) and x = t .
1 , x2 , .
, xn ) OO .
, .
n the indicator vector of hyperedges in E(HG ) that corresponds to the family C, that is, xi is equal to 1 if Ei OO C, and otherwise 0.
We see that C is a cointerval edge covering of G if and only if MG x Ou 1 holds, where 1 is a vector of all ones.
We note that a subgraph of G with only one edge is a cointerval subgraph of G.
Hence the boxicity of a graph G can be deAned as the optimum value of the integer program .
hat is feasibl.
(IP) minimize t 1x subject to MG x Ou 1 and x OO .
, .
n , that is, box(G) = min.
1x : MG x Ou 1, x OO .
, .
n }.
We relax the condition of the integer program (IP) and consider the linear program (LP) minimize t 1x subject to MG x Ou 1 and x Ou o.
A note on lower bounds for boxicity of graphs Kamibeppu where o is a zero vector.
We deAne the fractional boxicity of a graph G, denoted by boxf (G), to be the optimum value of (LP), that is, boxf (G) = min.
1x : MG x Ou 1, x Ou .
Hence boxf (G) O box(G) holds for a graph G.
By the way, in the theory of linear programming, we usually consider the dual program of (LP):
(D) maximize t 1y subject to t MG y O 1 and y Ou o.
The program (D) is clearly feasible.
It is well-known in the theory of linear programming that a feasible linear program and its dual feasible program have the same optimum value.
Hence we may consider the value of (D) instead of boxf (G).
We notice that a vector yO of all 1/pAos is a feasible solution of (D), where p = maxEi OOE(HG ) |Ei |.
Hence, boxf (G) Ou t 1yO = |E(G)|/p.
We note that this lower bound for fractional boxicity of graphs is identical to the lower bound for boxicity of graphs in Lemma 1.
An automorphism of a hypergraph H is a bijection A on V (H) such that X OO E(H) if and only if A(X) OO E(H).
A hypergraph H is vertex-transitive .
dge-transitiv.
if for every pair .
1 , w2 ) of vertices .
there exists an automorphism A of H such that A.
1 ) = w2 holds.
The following theorem is derived from Proposition 1.
4 in .
Theorem 2.
For a graph G, the inequalities box(G) Ou boxf (G) Ou
|E(G)|
maxEi OOE(HG ) |Ei | In particular, if G is edge-transitive, we have the equality boxf (G) = |E(G)| maxEi OOE(HG ) |Ei | Proof.
Note that the fractional boxicity of a graph G is the same concept with the fractional covering number of the hypergraph HG .
In Lemma 2.
2 below, we show the hypergraph HG is vertextransitive by the edge-transitivity of G, so the above equality holds by Proposition 1.
4 in .
The following Lemma 2.
2 completes the proof of this theorem.
Lemma 2.
If G is edge-transitive for a graph G, the hypergraph HG is vertex-transitive.
Proof.
For every pair of vertices e1 , e2 OO V (HG ) = E(G), there exists an automorphism A :
V (G) Ie V (G) such that A.
1 ) = e2 holds by our assumption.
We can check that A induces a bijection A on E(G) in a natural way: A.
= A.
for an edge uv OO E(G).
Moreover E is in E(HG ) if and only if A(E) is in E(HG ) since A and its inverse A Oe1 map a subgraph H of G to a subgraph isomorphic to H.
Hence A is the desired map.
A note on lower bounds for boxicity of graphs Kamibeppu The fractional boxicity of a graph G is the same as the maximum value of t 1y under the conditions t MG y O 1 and y Ou o.
We note that each entry of y is a weight of an edge of G.
The rows of t MG are indexed by all cointerval subgraphs of G, but we see that A an inequality in t MG y O 1 corresponding to a non-maximal cointerval subgraph .
n their edge set.
is superCuous since y Ou o.
Hence we only have to focus on maximal cointerval subgraphs of G when we calculate boxf (G).
what follows.
MG always means the .
incidence matrix of HG whose columns are indexed by all maximal cointerval subgraphs of G.
The boxicity and the fractional boxicity of a graph are different in general .
lso see Example 2.
and Remark 2.
As a simple example, let us consider the graph G in Figure 1 whose complement is isomorphic to K3 with a pendant edge added at each vertex of K3 .
It is easy to see that box(G) = 2 > 3/2 Ou boxf (G) holds.
Figure 1.
The graph G .
and its complement G .
We can And three maximal cointerval subgraphs of G in total, each of which is isomorphic to the graph obtained from G by deleting one pendant edge.
It is easy to check that x = .
/2, 1/2, 1/.
is a feasible solution for MG x Ou 1 and x Ou o.
Hence boxf (G) O t 1x = 3/2.
We will reduce unnecessary restrictions further within the same conditions MG x Ou 1 and x Ou o.
Let E (OC E(HG )) be the family of all maximal cointerval subgraphs of G.
Write Fe = {E OO E : e OO E} for an edge e OO E(G).
An edge e of G is said to be fundamental if Fe is minimal as subfamily of E .
ee heavy edges in Figure 1 for deAnitio.
Let E O be the set of all fundamental edges of G.
We deAne two edges e and eA in E O to be equivalent, denoted by e O eA , if Fe = FeA .
We remark that A an inequality in MG x Ou 1 corresponding to a non-fundamental edge of G is superCuous since x Ou o, and A if e O eA for e, eA OO E O , the two inequalities in MG x Ou 1 which correspond to e and eA are the same inequalities.
The inequality corresponding to an equivalence class .
means an inequality in MG x Ou 1 corresponding to a representative of .
It does not depend on the choice of representatives of .
Let MGO be the reduced incidence matrix of HG whose rows are indexed by all equivalence classes in E O /O and whose columns are indexed by all maximal cointerval subgraphs of G.
We see that A MG x Ou 1 is equivalent to MGO x Ou 1 under x Ou o.
A note on lower bounds for boxicity of graphs Kamibeppu Hence the fractional boxicity of a graph G is the same as the optimum value of the linear program (LP)A minimize t 1x subject to MGO x Ou 1 and x Ou o.
We consider a relaxation program of (LP)A and get a natural lower bound for fractional boxicity of graphs.
Theorem 2.
For a graph G, let {H1 .
H2 , .
Hl } be the family of all maximal cointerval subgraphs of G and let E O /O = {.
1 ], .
2 ], .
, .
k ]}.
Let ai be the number of fundamental edges of G in .
1 , e2 , .
, ek } which are contained in Hi for i OO .
, 2, .
, .
Then boxf (G) Ou aO holds, where aO = max.
1 , a2 , .
, al }.
Proof.
Note that boxf (G) = min.
1x : MGO x Ou 1, x Ou .
Sum up all k inequalities in MGO x Ou 1, and then we obtain aO .
= aO .
1 x2 A A A xl ) Ou a1 x1 a2 x2 A A A al xl Ou k, where x = t .
1 , x2 , .
, xl ).
Hence t 1x Ou k/aO holds, that is, boxf (G) Ou k/aO .
The fractional boxicity of a graph will measure its boxicity more accurately than the other lower bounds for boxicity given by Adiga et al.
in 2014, although it is a difAcult parameter to estimate by examination like the other fractional graph invariants.
Example 2.
We consider the graph Gk whose complement is the graph in Figure 2 below .
nd is not edge-transitiv.
, where k Ou 4.
We will And all maximal cointerval subgraphs of Gk and prove boxf (Gk ) = k/2.
Let H be a cointerval subgraph of Gk .
For example, we see that .
H cannot have edges e11 , e12 , .
, e5kOe9 if H has the edge e1 , and .
H cannot have edges e16 , e17 , .
, e5kOe9 if H has at least one of e2 , e3 , e4 and e5 .
We will obtain similar statements to .
if H has an edge ei , where i OO .
, 7, .
, 5.
Case 1.
Assume that H contains the edge e1 .
If it has at least one of e7 , e8 , e9 and e10 , we can And maximal cointerval graphs containing H within the graph induced by .
1 , .
, v6 , v2kOe1 , v2k }, and otherwise we can And them within the graph induced by .
1 , v2 , v3 , v4 , v2kOe3 , v2kOe2 , v2kOe1 , v2k }.
Case 2.
Assume that H has at least one of e2 , e3 , e4 and e5 .
If it has at least one of e12 , e13 , e14 and e15 , we can And maximal cointerval graphs containing H within the graph induced by .
1 , .
, v8 }, and otherwise we can And them within the graph induced by .
1 , .
, v6 , v2kOe3 , v2kOe2 , v2kOe1 , v2k }.
As a result it is sufAcient to And maximal cointerval subgraphs of the graph HO in Figure 3.
Clearly.
HO and HO Oe e .
hat is obtained from HO by deleting .
are not cointerval for any e OO E(HO ).
A note on lower bounds for boxicity of graphs Kamibeppu e5kOe3 e5kOe1 v2kOe1 e5kOe2 e5kOe4 e5kOe8 e5kOe6 e5kOe5 v2kOe2 e5kOe7 v2kOe3 e5kOe9 Figure 2.
The complement of the graph Gk .
will And three maximal cointerval subgraphs of HO , but two of them can be extended to the graph isomorphic to the graph with heavy edges in Figure 3 on the graph Gk .
We have k maximal cointerval subgraphs of Gk in total, each of which is isomorphic to the graph with heavy edges in Figure 3.
Hence the optimum value of the following linear program becomes the fractional boxicity boxf (Gk ).
(D) maximize subject to y1 y2 A A A y5k y1 y2 A A A y10 y5kOe3 y5kOe2 A A A y5k O 1 y5iOe13 y5iOe12 A A A y5i O 1 .
OO .
, 4, .
, .
) y1 y2 A A A y5 y5kOe8 y5kOe7 A A A y5k O 1 yj Ou 0 .
OO .
, 2, .
, 5.
) Figure 3.
The graph HO .
and its maximal cointerval subgraphs .
A note on lower bounds for boxicity of graphs Kamibeppu We consider the dual program of (D) and reduce superCuous inequalities so that we can obtain the following linear program:
(LP)A minimize subject to x1 x2 A A A xk x1 xk Ou 1 xi xi 1 Ou 1 .
OO .
, 2, .
, k Oe .
) xj Ou 0 .
OO .
, 2, .
, .
Then .
1 , x2 , .
, xk ) = .
/2, 1/2, .
, 1/.
is a feasible solution of (LP)A , and hence boxf (Gk ) O k/2.
Let E O be the set of all fundamental edges of Gk .
It is easy to check that A E O = .
1 , e6 , .
, e5kOe4 }.
A E O /O = {.
1 ], .
6 ], .
, .
5kOe4 ]} holds because e = eA implies e O eA for e, eA OO E O , and A aO = 2 since every maximal cointerval subgraph of Gk contains two fundamental edges in .
1 , e6 , .
, e5kOe4 }.
By Theorem 2.
3, boxf (Gk ) Ou k/2 holds, which implies our claim.
Remark 2.
oxf vs.
the lower bounds in Lemmas 1.
1 and 1.
It is easy to see that box(Gk ) O UOk/2UO holds for any k by Theorem 1.
Hence box(Gk ) = UOk/2UO holds since boxf (Gk ) = k/2.
The lower bounds for boxicity in Lemmas 1.
1 and 1.
2 do not work on the graph Gk well for k Ou 7, that is, they cannot determine the boxicity of Gk .
We see that boxf (Gk ) > 5k/14 = |E(Gk )|/ maxEi OOE(HGk ) |Ei | holds.
Let m(Gk ) be the maximum number of edges ai bi of Gk with the condition in Lemma 1.
2 and let Mk be a set of those edges of Gk .
For example, if e1 OO Mk , any edge in .
2 , e3 , .
, e10 , e5kOe8 , e5kOe7 , .
, e5k } cannot be in Mk .
If an edge e OO .
2 , e3 , e4 , e5 } is in Mk , any edge in .
1 , e2 , .
, e11 , e5kOe4 , e5kOe3 , .
, e5k }\.
cannot be in Mk .
It is not difAcult to see that m(Gk ) O k/2 holds in any case.
Hence we have UOm(Gk )/2UO O UOk/4UO < boxf (Gk ).
The difference between the fractional boxicity boxf (Gk ) and |E(Gk )|/ maxEi OOE(HGk ) |Ei | .
r UOm(Gk )/2UO) can be arbitrary large.
Further Observation Finally we remark another way to calculate the fractional boxicity of graphs.
Let s be a positive integer.
The s-fold boxicity of a graph G, denoted by boxs (G), is the minimum cardinality of a multiset {E1 .
E2 , .
Ek } of cointerval subgraphs of G such that each edge of G is in at least s cointerval subgraphs in the multiset.
Note that box1 (G) = box(G).
Since the subadditivity boxs t (G) O boxs (G) boxt (G) holds for a graph G and s, t Ou 1, the following limit exists and we have the following equality by FeketeAos subadditivity lemma .
boxs (G) boxs (G) = inf :sOu1 .
sIeO A note on lower bounds for boxicity of graphs Kamibeppu Lemma 3.
1 (.
Let Z and R be the set of all nonnegative integers and the set of all nonnegative real numbers, respectively.
If g : Z Ie R is subadditive, that is, g.
O g.
holds for any m, n OO Z , the limit limmIeO g.
/m exists and is equal to inf g.
/m.
A basic result on the fractional covering numbers of hypergraphs guarantees boxf (G) = limsIeO boxs (G)/s .
ee Theorem 1.
1 in .
Hence we may approach the study on the s-fold boxicity of graphs to calculate the fractional boxicity of graphs.
Acknowledgments This work was initiated while the author was supported by JSPS KAKENHI Grant-in-Aid for Young Scientists (B).
No.
This paper was signiAcantly improved thanks to comments and suggestions from anonymous referees who were involved in the reviews.
The author would like to show all anonymous referees my gratitude for his or her careful reading and References