ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 293-297
On the connectivity of Cartesian product of
graphs*
Jelena Govorčin
Faculty of information studies Ulica talcev 3, 8000 Novo mesto, Slovenia
Riste Skrekovski
Department of Mathematics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia
Received 29 February 2012, accepted 29 October 2012, published online 7 May 2013
We give a new alternative proof of Liouville's formula which states that for any graphs G and H on at least two vertices, k(GDH) = min {k(G)|H|, |G|k(H), ¿(G) + S(H)}, where k and S denote the connectivity number and minimum degree of a given graph, respectively. The main idea of our proof is based on construction of a vertex-fan which connects a vertex from V(GdH) to a subgraph of GnH. We also discuss the edge version of this problem as well as formula for products with more than two factors.
Keywords: Connectivity, Cartesian product. Math. Subj. Class.: 05C40, 05C76
1 Introduction
The Cartesian product has been studied extensively since the 1950's. Despite of its simple definition, answering many underlying questions is far from being trivial. One such question refers to a connectivity of a Cartesian product and how it depends on invariants of its factors.
The first result of this type appeared in an article written by Sabidussi [5] in 1957. He proved that for arbitrary graphs G and H, «(GdH) > k(G) + k(H). In 1978, Li-ouville [4] conjectured that for graphs G and H on at least two vertices, k(GDH) = min {k(G) |H|, |G|k(H), S(G) + S(H)}, where k and S denote the connectivity number
* Partially supported by ARRS project L7-4119 and ARRS research programs P1-0383. E-mail addresses: jelena.govorcin@fis.unm.si (Jelena Govorcin), skrekovski@gmail.com (Riste Skrekovski)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
Abstract
488
ArsMath. Contemp. 7(2014)487-497
and minimum degree of a given graph, respectively. The result of Subidussi was improved by Xu and Yang [7]. They showed that k(GDH) > min {k(G) + ¿(H), k(H) + ¿(G)}, where G and H are connected undirected graphs. Finally, the Liouville's formula has been recently proved by Spacapan in [6]. For more information on the topic, see also [1, 2, 3].
We use the following terminology. The Cartesian product of two graphs G and H, denoted by GdH, is a graph with vertex set V(G) x V(H), where two vertices (g, h) and (g', h') are adjacent if gg' e E(G) and h = h' or g = g' and hh' e E(H). The graphs G and H are called the factors of GdH. For any h e V (H), we denote by Gh the subgraph of GDH induced by V(G) x {h} and name it G-fiber. Similarly, we can define H-fiber.
For a graph G and v e V(G), the degree of a vertex v is denoted by dG(v), or simply d(v) if the graph G is known from the context. Furthermore, we denote by ¿(G) the minimum degree of a graph G. The minimum degree is additive under Cartesian products, i.e. ¿(GdH) = ¿(G) + ¿(H). Recall that the symbol NG(v) denotes the set of neighbours of a vertex v in a graph G.
For a connected graph G a subset S C V(G) is a separating set if G - S has more than one component. The connectivity k(G) of G is the minimum size of S C V(G) such that G - S is disconnected or a single vertex. For any k < k(G), we say that G is k-connected. A subset of edges S' C E(G) is disconnecting set if G - S' has more than one component. The edge-connectivity A(G) of G is the maximum k for which G is k-edge-connected, i.e. every disconnecting set consists of at least k edges.
A set of (u, W)-paths, where W c V(G) and u e V(G) \ W, is called a vertex-fan (resp. an edge-fan) if any two of the considered paths have only vertex u in common (resp. edge-disjoint paths). We say that a vertex-fan avoids a vertex v if its paths do not contain v.
In this paper, we provide an alternative poof of Liouville's formula. Our approach to proving this result includes construction of a vertex-fan which connects a vertex from V(GdH) to a subgraph of GdH. Namely, for every vertex (a, b) e V(GdH) there exists a vertex-fan of minimum size d(a) + d(b) which connects a chosen vertex and a connected subgraph of GdH comprised of a fiber of G and a fiber of H. We also discuss the edge version of this problem as well as formula for products with more than two factors.
2 Connectivity of Cartesian product
Here, we construct the fan.
Proposition 2.1. Let G and H be connected graphs, a, c e V(G) and b, d e V(H) distinct vertices. Then, there exists a vertex-fan F from (a, b) to Gd U cH of size d(a) + d(b) that avoids the vertex (c, d). Moreover d(a) paths of F are ended in Gd and d(b) paths of F are ended in cH.
Proof. Let NG(a) = {ai, a2,..., ad(o)} and Nh(b) = {bi, b2,..., bd(6)}. Let PG = axix2x3 • • • xk(= c) (resp. PH = by1y2y3 • • • yi(= d)) be a shortest path that connects a and c in G (resp. b and d in H). Thus, x1 (resp. y1) is the only neighbour of a (resp. b) that is contained in PG (resp. PH). So, without loss of generality, we can assume that xi — ai and yi = bi.
Now, we construct a vertex-fan F from (a, b) to Gd U cH. First, we define d(a) vertex-
J. Govorcin andR. Skrekovski: On the connectivity of Cartesian product of graphs
295
disjoint paths that use copies of the path PH to reach the fiber Gd:
(a,b)PaH	where P*h = (a,yi)(a,y2)(a,ys) ■■■ (a,y—)(a,d),
(a,b)(ai,b)Paih where P*ih = (ai,yi)(ai,y2)(ai,ys) ■■■ (ai,yt-i)(aud),
i = 2, 3,..., d(a). Furthermore, we construct d(b) vertex-disjoint paths that use copies of the path PG to reach the fiber cH. For every j = 2, 3,..., d(b) define:
(a,b)PGb	where PGb = (xi,b)(x2,b)(x3,b) ■■■ (xk-i,b)(c,b),
(a, b)(a, bj )PGbi where PGbj = (x1,bj )(x2,bj )(x3,bj) ■■■ (xk-i,bj )(c,bj).
As can be easily seen from the construction, defined paths are vertex disjoint and none contains the vertex ( c, d) .
□
Now, we prove the formula.
Theorem 2.2. Let G and H be graphs on at least two vertices. Then,
k(GUH) = min{k(G)IH|, GIk(H), 6(G) + 5(H)} .
Proof. First we show that k(GUH) is at most the claimed minimum. Let S be a separating set of the graph G. Then S x V(H) is a separating set of GUH. Consequently, k(GUH) < k(G)H| and analogously, k(GUH) < k(H)|G|. Since k(GUH) < 5(GUH) = 6(G) + 6(H), it follows that k(GUH) < min{k(G)IH|, GIk(H), 6(G) + 6(H)} and we have shown desired inequality.
Now, we show that k(GUH) is at least the claimed minimum. Suppose it is false and GUH has a separating set S with |S| < min{k(G)H|, GIk(H), 6(G) + 6(H)} . Then, there exist vertices c G V(G) and d G V(H) such that |V(Gd) n S| < k(G) and |V(cH) n S| < k(H). In particular, Gd - S and cH - S are connected.
Notice that Proposition 2.1 implies that each vertex of GUH - S is connected to Gd U cH by a path avoiding S. Hence, if (c, d) G S, then Gd U cH - S is connected, and so is GUH - S.
So assume (c, d) G S. Then GUH - S has at most two components, one containing Gd - S and other containing cH - S. Now we will find a vertex adjacent to both of these subgraphs, and this will imply connectedness of GUH - S.
If we can choose ci g NG(c) and d\ G NH(d) such that none of vertices (c, d\), (c1,d1), (ci, d) belongs to S, then (ci, di) connects Gd - S and cH - S and hence connectedness of GUH - S follows. Suppose that we cannot make such a choice. Let x (resp. y) be the number of neighbours of (c, d) in Gd - S (resp. cH - S). Then x y vertices from NG(c) x NH(d) must be in S, because of the assumption. So there are at least dG(c) - x + dH(d) - y + xy + 1 vertices in S.
By the assumption on S, dG(c) - x + dH(d) - y + xy + 1 < 6(G) + 6(H) < dG(c) + dH(d) and after simple transformation one can obtain xy + 1 < x + y. But the latter inequality holds if and only if x = 0 or y = 0. Since k(G) < 6(G), this contradicts the assumptions that both fibers Gd and cH contain less than k(G) resp. k(H) vertices of S.
Hence, we showed that Gd U cH - S is connected, and so is GUH - S. Therefore,
ISI > 6(G) + 6(H).	□
402
Ars Math. Contemp. 7 (2014) 379-187
We discuss the edge version of this problem. A similar result for the edge-connectivity of the Cartesian product was proved by Xu and Yang [7] in 2006 using the edge version of Menger's theorem:
Theorem 2.3. Let G and H be graphs on at least two vertices. Then,
A (GOH ) = min |A(G)|H |, |G|A(H ), 0(G) + 5(H )} . In 2008 new short version of the proof, avoiding Menger's theorem, appeared in [3].
We can use the fan from Proposition 2.1 and a very simplified argument of Theorem 2.2 (mainly the first two paragraphs) to prove Theorem 2.3. Moreover, instead of the fan of Proposition 2.1, we can use the following simpler one (using notation from the proof of Proposition 2.1): for every i = 1,2,..., d(a) define:
(a,b)(ai,b)Pai H, where P*i h = (ai, yi)(ai, )(a» ,y3) ••• (ai,yi-i)(ai, d),
and for every j = 1,2,..., d(b) define
(a,b)(a,bj )PGbj, where PG b6 = (xi ,bj )(x2 ,bj )(x3,bj ) ••• (xfc_i,bj )(c,bj ).
It is easy to see that this is an edge-fan of size d(a) + d(b) from (a, b) to Gd U cH.
Finally, we would like to stress that above approach enables us to generalize Liouville's formula for Cartesian products with more than two factors. We state this result in the following theorem.
Theorem 2.4. Let Gi, i = 1,2,... ,n be graphs on at least two vertices and let G = G1DG2□ ••• □ Gn. Then,
k(G) = k(G^ ••• □G„)=miJ |G|, ...	|G|,5(Gi) + ••• + ¿(G„)l.
I |G1|	1 Gn1	J
Proof. We prove given equality using induction on the number of factors n. The base case for n = 2 is proved in Theorem 2.2. In order to prove that equality holds for n, we consider k(G) = k(G1^ • • • □Gn) as the Cartesian product of two graphs G' = G1^ • • • □Gn-1 and Gn.
Then, by the induction hypothesis,
«(G'^G„)=min{«(G')|Gn|, K(G„)|G'|, S(G') + ¿(Gn)}
= min {k(G')|G„|, KG) |G|, S(G1) + • • • + ¿(Gn-1) + ¿(Gn)} = min { ^ |G|, ... , ^^ |G|, Kg]1 |G|, ¿(G1) + ••• + S(Gn)}
where the last equality holds by the induction hypothesis applied on k(G') = k(G1^ • • •
□Gn-1) and an obvious inequality J(G1)+-----+ S(Gn) < (J(G1)H-----+ ¿(Gn-1))|Gn|.
□
Regarding the above formula, if all Gi's are isomorphic to a graph H, then we obtain the formula
K(Hn) = min {k(H)|H|n-1, nJ(H)} = nJ(H), which was observed in [3].
J. Govorcin andR. Skrekovski: On the connectivity of Cartesian product of graphs	297
References
[1]	W. Imrich, S. KlavZar and D. F. Rail, Topics in Graph Theory: Graphs and Their Cartesian Product, AK Peters, Ltd., Wellesley, MA, 2008.
[2]	S. KlavZar, Recent Developments on the Structure of Cartesian Products of Graphs, RMS-Lecture Notes Series No. 13 (2010), 171-177.
[3]	S. KlavZar and S. Spacapan, On the edge-connectivity of Cartesian product graphs, Asian-European J. Math. 1 (2008), 93-98.
[4]	B. Liouville, Sur la connectivite des produits de graphes, C. R. Acad. Sci. Paris Ser. A-B 286 (1978), A363-A365.
[5]	G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957), 515-525.
[6]	S. Spacapan, Connectivity of Cartesian product of graphs, Appl. Math. Lett. 21 (2008), 682-685.
[7]	J. -M. Xu and C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006), 159-165.