# Lexicographic Product and Isoperimetric Number

Authors: Ersin Aslan; Alpay Kirlangic
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Theisoperimetric number of a graph G, denoted by i(G), was introduced by Mohar (1987). A graph G and a subset X of its vertices are given, and let ∂(X) denote the edge boundary of X, the set of edges which connects vertices in X to vertices not in X. The isoperimetric number of G is defined as i(G)=min1≤|X|≤|V(G)|/2(|∂(X)|/|X|). In this paper, some results about the isoperimetric number of graphs obtained by graph operations are given.


---

## Body

## 1. Introduction

Given a graphG and a subset X of its vertices, let ∂(X) denote the edge boundary of X that is, the set of edges which connects vertices in X with vertices not in X. The isoperimetric number is defined as
(1)i(G)=min1≤|X|≤|V(G)|/2|∂(X)||X|.
Clearly, i(G) can be defined in a more symmetric form by
(2)i(G)=min|E(X,Y)|min{|X|,|Y|},
where the minimum runs over all partitions of V(G)=X∪Y into nonempty subsets X and Y, and E(X,Y)=∂X=∂Y are the edges between X and Y.As examples of isoperimetric numbers, we consider the following.(i)
The isoperimetric number of the complete graphKn with n vertices is i(Kn)=⌈n/2⌉.(ii)
The isoperimetric number of the cycleCn with n vertices is i(Cn)=2/⌊n/2⌋.(iii)
The isoperimetric number of the pathPn with n vertices is i(Pn)=1/⌊n/2⌋.(iv)
The isoperimetric number of the complete bipartite graph withm+n vertices Km,n is
(3)i(Km,n)={mnm+n,ifmandnareevenmn+1m+n,ifmandnareoddmnm+n-1,ifm+nisodd.It can be briefly shown as i(Km,n)=⌈mn/2⌉/⌊(m+n)/2⌋.The isoperimetric number is also closely related to the notion of bisection width,bw(G), of a graph G. This is the minimum number of edges that must be removed from G in order to split V(G) into two equal-sized (within one if the number of vertices in G is odd) subsets:
(4)bw(G)=min|X|=⌊|V(G)|/2⌋|∂X|,
where X⊂V(G). If known, one can use the isoperimetric number of a graph G to establish a lower bound for its bisection width using the fact that
(5)bw(G)⌊|V(G)|/2⌋≥i(G).See [1].The importance ofi(G) lies in various interesting interpretations of this number by Mohar as follows [2].(a)
From (2), it is evident that, in trying to determine i(G), we have to find a small edge-cut E(X,Y) separating as large a subset X (assume |X|≤|Y|) as possible from the remaining larger part Y. So, it is evident that i(G) can serve as measure of connectivity of graphs. It seems that there might be possible applications in problems concerning connected networks,and the ways to “destroy” them are by removing a large portion of the network by cutting only a few edges.(b)
The problem of the partitioningV(G) into two equally sized subsets (to within one element), in such a way that the number of the edges in the cut is minimal, is known as the bisectionwidth problem. It is important in VLSI design and some other practical applications. Clearly, it is related to isoperimetric number.Theorem 1 (see [2]).
Some of the theorems that Mohar stated are given below.(a)
i(G)=0 if and only if G is disconnected.(b)
IfG is k-edge-connected then i(G)≥2k/|V(G)|.(c)
Ifδ(G) is the minimal degree of vertices in G then i(G)≤δ(G).(d)
Ife=uv is an edge of G and |V(G)|≥4 then i(G)≤[deg(u)+deg(v)-2]/2.(e)
IfΔ is the maximum vertex degree in G then i(G)≤(Δ-2)+2/⌊|V(G)|/2⌋. If G has a cycle with almost half the vertices of G then i(G)≤Δ-2.If a setX⊂V(G) with |X|≤(1/2)|V(G)| reaches the minimum i(G)=|∂(X)|/|X| we call it an isoperimetric set. For U⊆V(G) denoted by G∣U, the subgraph of G is induced on U [2].Proposition 2 (see [2]).
IfG is a connected graph then it has an isoperimetric set X such that G∣X and G∣(V∖X) are connected subgraphs of G.In the next section, we prove a upper bound for isoperimetric number of lexicographic product of graphs.


## 2. Lexicographic Product

The lexicographic productG1[G2] of two graphs G1 and G2 has its vertex set V(G1)×V(G2) with (u1,u2) adjacent to (v1,v2) if either u1 adjacent to v1 in G1 or u1=v1 and u2 are adjacent to v2 in G2. Note that unlike the union, join, and Cartesian product, this operation is not commutative.Theorem 3.
LetG be a graph with m vertices, and let q edges and H be a graph with n vertices. Then,
(6)i(G[H])≤min{i(G)n,2q⌈n/2⌉m+bw(H)⌊n/2⌋}.Proof.
LetXG⊆V(G) and XG be the isoperimetric set of G and ∂G(X) edge boundary of G. We know that G[H] includes n copies of G. If |X|=|XG|n then |∂(X)|≤|∂G(X)|nn. Hence,
(7)|∂(X)||X|≤|∂G(X)|nn|XG|n=|∂G(X)|nn|XG|n=|∂G(X)|n|XG|.
So,
(8)min{|∂(X)||X|}≤min{|∂G(X)|n|XG|}=min{|∂G(X)||XG|}n=i(G)n.
Similarly, letXH⊆V(H) with |XH|≤⌊n/2⌋ and |XH|=rm. We know that G[H] includes m copies of H. If |X|=rm then we have |∂(X)|≤r(n-r)2q+|∂H(X)|m. Therefore, |∂(X)|/|X|≤(r(n-r)2q+|∂H(X)|m)/rm. So, min{|∂(X)|/|X|}≤min{(r(n-r)2q+|∂H(X)|m)/rm}. The function (r(n-r)2q+|∂H(X)|m)/rm takes its minimum value at r=⌊n/2⌋. Since |XH|=⌊n/2⌋ then |∂(X)|=bw(H). We have
(9)i(G[H])≤2q⌈n/2⌉m+bw(H)⌊n/2⌋.
The proof is completed by (8) and (9).We havei(G)n≤2q⌈n/2⌉)/m+bw(H)/⌊n/2⌋according to the upper bounds of i(G), and hence we get i(G[H])≤i(G)n.Corollary 4.
LetG be a graph with m vertices, and let q edges and H be a graph with n vertices. If n is even and i(G)≤q/m and i(G)≤2bw(H)n2 then
(10)i(G)n≤2q⌈n/2⌉m+bw(H)⌊n/2⌋.Proof.
Ifn is even and i(G)≤2bw(H)/n2then i(G)n2≤2bw(H). Hence, we have i(G)n2+qn2≤2bw(H)+qn2. Since i(G)≤q/m then n2(i(G)+i(G)m)≤ n2(i(G)+q)≤i(G)n2+qn2≤2bw(H)+qn2. So, we have i(G)mn2≤n2(i(G)+i(G)m)≤2bw(H)+qn2. Therefore, we have
(11)i(G)mn2mn≤2bw(H)+qn2mn=2q(n/2)m+bw(H)n/2=2q⌈n/2⌉m+bw(H)⌊n/2⌋.Corollary 5.
LetG be a graph with m vertices, and let q edges and H be a graph with n vertices. If n is odd and i(G)≤2bw(H)n2-n then
(12)i(G)n≤2q⌈n/2⌉m+bw(H)⌊n/2⌋.Corollary 6.
LetT be a tree with m vertices, and let H be a graph with n vertices. If n is even then
(13)i(T)n≤2(m-1)⌈n/2⌉m+bw(H)⌊n/2⌋.Proof.
Forn>1 and m>1, we know that 0≤(m-2)n2+2m. Then, mn2≤(2m-2)n2+2m. Since bw(H)≥1 and i(T)<1 then we have i(T)mn2≤mn2≤(2m-2)n2+2mbw(H). Therefore, we have
(14)i(T)n≤2(m-1)(n/2)m+bw(H)n/2=2(m-1)⌈n/2⌉m+bw(H)⌊n/2⌋.Corollary 7.
LetT be a tree with m vertices, and let H be a graph with n vertices. If n is odd and n-1<m then i(T)n≤2(m-1)⌈n/2⌉/m+bw(H)/⌊n/2⌋.Corollary 8.
LetG be a graph with m vertices, q edges that is not a tree, and let Pn be a path graph with n vertices. If n is even and i(G)≤(m-1)/m then
(15)i(G)n≤2q(n/2)m+1(n/2)=2q⌈n/2⌉m+bw(Pn)⌊n/2⌋.Proof.
Ifn is even and i(G)≤(m-1)/m then i(G)m≤m-1. Thus, i(G)mn2≤(m-1)n2≤(m-1)n2+2m. Therefore, i(G)mn^2/mn≤((m-1)n^2+2m)/mn=(m-1)n/m+2/n. So,
(16)i(G)n≤(m-1)nm+2n=2(m-1)n/2m+1n/2≤2q(n/2)m+1n/2=2q⌈n/2⌉m+bw(Pn)⌊n/2⌋.Corollary 9.
LetG be a graph with m vertices, q edges that is not a tree, and let Pn be a path graph with n vertices. If n is odd and i(G)≤2/(n^2-n) then
(17)i(G)n≤2q((n+1)/2)m+1(n-1)/2=2q⌈n/2⌉m+bw(Pn)⌊n/2⌋.Corollary 10.
LetG be a graph with m vertices, q edges that is not a tree, and let Cn be a cycle graph with n vertices. If n is even and i(G)≤(n^2+4)/n^2then
(18)i(G)n≤2q(n/2)m+2n/2=2q⌈n/2⌉m+bw(Cn)⌊n/2⌋.Proof.
Ifn is even and i(G)≤(n^2+4)/n^2then
(19)i(G)n≤n2+4n=n2n+4n=mnm+2n/2=2mn/2m+2n/2≤2q(n/2)m+2n/2.
So,
(20)i(G)n≤2q(n/2)m+2n/2=2q⌈n/2⌉m+bw(Cn)⌊n/2⌋.Corollary 11.
LetG be a graph with m vertices, q edges that is not a tree, and let Cn be a cycle graph with n vertices. If n is odd and i(G)≤(n^2+3)/(n^2-n) then
(21)i(G)n≤2q((n+1)/2)m+2(n-1)/2=2q⌈n/2⌉m+bw(Cn)⌊n/2⌋.Corollary 12.
LetG be a graph with m vertices, q edges that is not a tree and let Kn be a complete graph with n vertices.(a)
Ifn is even and i(G)≤(q/m)+(1/2) then
(22)i(G)n≤2q(n/2)m+n2/4n/2=2q⌈n/2⌉m+bw(Kn)⌊n/2⌋.(b)
Ifn is odd and i(G)≤(n+1)(2q+m)/mn then
(23)i(G)n≤2q⌈n/2⌉m+bw(Kn)⌊n/2⌋.Proof.
(a) Ifn is even and i(G)≤(q/m)+(1/2) then we have
(24)i(G)n≤qnm+n2=2q(n/2)m+n2/4n/2=2q⌈n/2⌉m+bw(Kn)⌊n/2⌋.
The proof for n even is very similar to the proof for odd.Theorem 13.
LetPm be a path graph with m vertices, and let q edges and H be a graph with n vertices. Then,
(25)i(Pm[H])={2nm,ifmiseven2n2+2bw(H)mn,ifmisoddandnisevenandbw(H)(m-1)<n22nm-1,ifmisoddandnisevenandbw(H)(m-1)≥n22n2+2bw(H)mn-1,ifmandnareoddandbw(H)(m-1)<n2-n2nm-1,ifmandnareevenandbw(H)(m-1)≥n2-n.Proof.
LetV(Pm)={1,2,…,m} and X⊆V(Pm[H]) with |X|≤⌊mn/2⌋. For i=1,2,…,m let Xi=X∩(V(H)×i). Hence, X is the disjoint union of X1,X2,…,Xm. Let S0={Xi∣|Xi|=0,1≤i≤m} and Sn={Xi∣|Xi|=n,1≤i≤m}. To prove this theorem, we have three cases.
Case  1. Let m be an even integer. To prove this case, we have three subcases.
Subcase 1.1. If |X|=r where 1≤r<n then |∂(X)|≥rn+1. Therefore, |∂(X)|/|X|≥(rn+1)/r. The function (rn+1)/r has its minimum value at r=n-1, and we have
(26)min{|∂(X)||X|}≥(n-1)n+1n-1.
Subcase 1.2. If S0>0 and Sn>0 and |X|=r where n≤r≤mn/2 then |∂(X)|≥n2+(m-S0-Sn)|∂H(X)|. Therefore, |∂(X)|/|X|≥(n2+(m-S0-Sn)|∂H(X)|)/r. The function (n2+(m-S0-Sn)|∂H(X)|)/r has its minimum value at r=mn/2. If r=mn/2 then (m-S0-Sn)|∂H(X)|=0. Thus,
(27)min{|∂(X)||X|}≥2nm.
Subcase 1.3. If (S0=0,Sn=0) or (S0=0,Sn>0) or (S0>0,Sn=0) and |X|=r where n≤r≤mn/2 then
(28)|∂(X)|≥⌊rm⌋(n-⌊rm⌋)2q+|∂H(X)|m≥⌊rm⌋(n-⌊rm⌋)2(m-1)+|∂H(X)|m≥⌊rm⌋(n-⌊rm⌋)(2m-2)+m.
Thus, |∂(X)|/|X|≥(⌊r/m⌋(n-⌊r/m⌋)(2m-2)+m)/r. The function (⌊r/m⌋(n-⌊r/m⌋)(2m-2)+m)/r has its minimum value at r=mn/2, and we have
(29)min{|∂(X)||X|}≥⌊(mn/2)/m⌋(n-⌊(mn/2)/m⌋)(2m-2)+mmn/2=n2m-n2+2mmn.
By (26), (27), and (29), if m is even then i(Pm[H])=(2n/m).
Case  2. Let m be an odd, and let n be an even integer. To prove this case, we have four subcases.
Subcase 2.1. If |X|=r where 1≤r<n then |∂(X)|≥rn+1. Therefore, |∂(X)|/|X|≥(rn+1)/r. The function (rn+1)/r has its minimum value at r=n-1, and we have
(30)min{|∂(X)||X|}≥(n-1)n+1n-1.
Subcase 2.2. If S0>0 and Sn>0 and |X|=r where n≤r≤(m-1)n/2 then |∂(X)|≥n^2+(m-S0-Sn)|∂H(X)|. Therefore, |∂(X)|/|X|≥(n^2+(m-S0-Sn)|∂H(X)|)/r. The function (n^2+(m-S0-Sn)|∂H(X)|)/r has its minimum value at r=(m-1)n/2. If r=(m-1)n/2 then (m-S0-Sn)|∂H(X)|=0. Thus,
(31)min{|∂(X)||X|}≥n2(m-1)n/2=2nm-1.
Subcase 2.3. If S0>0 and Sn>0 and |X|=r where (m-1)n/2≤r≤mn/2 then |∂(X)|=n2+bw(H). Therefore, |∂(X)|/|X|=(n^2+bw(H))/r. The function (n^2+bw(H))/r has its minimum value at r=mn/2. Thus,
(32)min{|∂(X)||X|}=n2+bw(H)mn/2=2n2+2bw(H)mn.
Subcase 2.4. If (S0=0,Sn=0) or (S0=0,Sn>0) or (S0>0,Sn=0) and |X|=r where n≤r≤mn/2 then
(33)|∂(X)|≥⌊rm⌋(n-⌊rm⌋)2q+|∂H(X)|m≥⌊rm⌋(n-⌊rm⌋)2(m-1)+|∂H(X)|m≥⌊rm⌋(n-⌊rm⌋)(2m-2)+m.
Thus, |∂(X)|/|X|≥(⌊r/m⌋(n-⌊r/m⌋)(2m-2)+m)/r. The function (⌊r/m⌋(n-⌊r/m⌋)(2m-2)+m)/r takes minimum value at r=mn/2, and we have
(34)min{|∂(X)||X|}≥⌊(mn/2)/m⌋(n-⌊(mn/2)/m⌋)(2m-2)+mmn/2=n2m-n2+2mmn.
By (30), (31), (32), and (34), we have that if m is odd and n is even and bw(H)(m-1)<n2 then i(Pm[H])=(2n^2+2bw(H))/mn, and if m is odd and n is even and bw(H)(m-1)≥n2 then i(Pm[H])=2n/(m-1).
Case  3. The proofs of the case in which m and n are odd are similar to that of Case 2.The isoperimetric number ofi(Pm[Pn]) is given in the following corollary.Corollary 14.
Letm and n be positive integers. Then,
(35)i(Pm[Pn])={2nm,ifmiseven2n2+2mn,ifmisoddandnisevenand(m-1)<n22nm-1,ifmisoddandnisevenand(m-1)≥n22n2+2mn-1,ifmisoddandnisoddand(m-1)<n2-n2nm-1,ifmisoddandnisevenand(m-1)≥n2-n.The isoperimetric number ofi(Pm[Cn]) is given in the following corollary.Corollary 15.
Letm>5 and n be positive integers. Then,
(36)i(Pm[Cn])={2nm,ifmiseven2n2+4mn,ifmisoddandnisevenand2(m-1)<n22nm-1,ifmisoddandnisevenand2(m-1)≥n22n2+4mn-1,ifmisoddandnisoddand2(m-1)<n2-n2nm-1,ifmisoddandnisevenand2(m-1)≥n2-n.The isoperimetric number ofi(Cm[Pn]) is given in the following corollary.Corollary 16.
Letm>5 and n be positive integers. Then,
(37)i(Cm[Pn])={4nm,ifmandnareevenandm>4n2n2+24n2+2mn,ifmisoddandnisevenandm≤2n2+14nm-1,ifmisoddandnisevenandm>2n2+1n2-1n,ifmisevenandnisoddandm≤4n2n2-14nm,ifmisevenandnisoddandm>4n2n2-14n2(m-1)n,ifmisoddandnisoddandm≤2n2-2n+14n2+2mn-1,ifmisoddandnisoddandm>2n2-2n+1.The isoperimetric number ofi(Km[Pn]) is given in the following corollary.Corollary 17.
Letm and n be positive integers. Then,
(38)i(Km[Pn])={n2m-n2+42n,ifnisevenn2m2-n2m+3m2mn,ifmisevenandnisoddn2m2-n2m+5m-12(mn-1),ifmandnareodd.The isoperimetric number ofi(K1,m[Pn]) is given in the following corollary.Corollary 18.
Letm and n be positive integers. Then,
(39)i(K1,m[Pn])={n2m+2m+2(m+1)n,ifnisevenand2m+2<n2n,ifnisevenand2m+2≥n2n2m+2m+3(m+1)n,ifnandmareoddand2m+3<n2n,ifnandmareoddand2m+3≥n2n2m+2m+2(m+1)n-1,ifnisoddandmisevenand2m+2<n2-nn,ifnisoddandmisevenand2m+2≥n2-n.The isoperimetric number ofi(K1,m[Cn]) is given in the following corollary.Corollary 19.
Letm and n be positive integers. Then,
(40)i(K1,m[Cn])={n2m+4m+4(m+1)n,ifnisevenand4m+4<n2n,ifnisevenand4m+4≥n2n2m+4m+5(m+1)n,ifnandmareoddand4m+5<n2n,ifnandmareoddand4m+5≥n2n2m+4m+4(m+1)n-1,ifnisoddandmisevenand4m+4<n2-nn,ifnisoddandmisevenand4m+4≥n2-n.



---

*Source: 243981-2013-09-02.xml*