A survey on the generalized connectivity of graphs
---
paper_title: Arboricity and spanning-tree packing of random graphs

paper_content:

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph G (n, p). For all p(n) ∈ [0, 1], we show that, with high probability, T is precisely the minimum between δ and bm/(n − 1)c, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals bm/(n−1)c and A equals dm/(n−1)e; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k →∞.
---
paper_title: On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

paper_content:

The problem of determining the smallest number of edges, $h(n;\bar{\kappa}\geq r)$, which guarantees that any graph with $n$ vertices and $h(n;\bar{\kappa}\geq r)$ edges will contain a pair of vertices joined by $r$ internally disjoint paths was posed by Erd\"{o}s and Gallai. Bollob\'{a}s considered the problem of determining the largest number of edges $f(n;\bar{\kappa}\leq \ell)$ for graphs with $n$ vertices and local connectivity at most $\ell$. One can see that $f(n;\bar{\kappa}\leq \ell)= h(n;\bar{\kappa}\geq \ell+1)-1$. These two problems had received a wide attention of many researchers in the last few decades. In the above problems, only pairs of vertices connected by internally disjoint paths are considered. In this paper, we study the number of internally disjoint Steiner trees connecting sets of vertices with cardinality at least 3.
---
paper_title: Lower bounds for the spanning tree numbers of two graph products

paper_content:

For any graph $G$ of order $n$, the spanning tree packing number \emph{$STP(G)$}, is the maximum number of edge-disjoint spanning trees contained in $G$. In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs.
---
paper_title: On edge-disjoint spanning trees in hypercubes

paper_content:

In this note we give a construction for obtaining the maximum number of edge-disjoint spanning trees in a hypercube. The result has applications to multicast communication in wormhole-routed parallel computers.
---
paper_title: The generalized 3-connectivity of Lexicographic product graphs

paper_content:

The generalized $k$-edge-connectivity $\lambda_k(G)$ of a graph $G$ is a generalization of the concept of edge-connectivity. The lexicographic product of two graphs $G$ and $H$, denoted by $G\circ H$, is an important graph product. In this paper, we mainly study the generalized 3-edge-connectivity of $G \circ H$, and get upper and lower bounds of $\lambda_3(G \circ H)$. Moreover, all bounds are sharp.
---
paper_title: Pendant tree-connectivity

paper_content:

Abstract A graph G is called ( k, n )-pendant tree-connected, iff for any subset A of the vertex set of G with cardinality k there exist n edge-disjoint trees T 1 ,…, T n which contain A as set of endvertices and are vertex-disjoint with the exception of A . This is a specialization of the tree-connectivity introduced in (M. Hager, Tree-connectivity in graphs, submitted) and includes the usual vertex-connectivity for k = 2. Necessary and sufficient conditions are given for a graph to be ( k , n )-pendant tree-connected proving that κ ( G )≥2 n ( k + 1) implies the ( k , n )-pendant tree-connectivity and k + n + 1 is a lower bound for this implication. Then we handle the case (3,2) showing that nonplanar graphs G with κ ( G )≥4, such that G -{ e } for some edge e is planar, are (3,2)-pendant tree-connected.
---
paper_title: Edge-disjoint spanning trees on the star network with applications to fault tolerance

paper_content:

Data communication and fault tolerance are important issues in parallel computers in which the processors are interconnected according to a specific topology. One way to achieve fault tolerant interprocessor communication is by exploiting the disjoint paths that exist between pairs of source and destination nodes. We construct n-1 directed edge disjoint spanning trees on the star network. These spanning trees are used to derive a near optimal single node broadcasting algorithm, and fault tolerant algorithms for the single node and multinode broadcasting, and for the single node and multinode scattering problems. Broadcasting is the distribution of the same group of messages from one processor to all the other processors. Scattering is the distribution of distinct groups of messages from one processor to all the other processors. We consider broadcasting and scattering from a single processor of the network and simultaneously from all processors of the network. The single node broadcasting algorithm offers a speed up of n-1 for a large number of messages, over the straightforward algorithm that uses a single shortest path spanning tree. Fault tolerance is achieved by transmitting the same messages through a number of edge disjoint spanning trees. The fault tolerant algorithms operate successfully in the presence of up to n-2 faulty nodes or edges in the network. No prior knowledge of the faulty nodes or edges is required. All of the algorithms operate under the store and forward, all port communication model.
---
paper_title: Tree-based multicasting in wormhole-routed irregular topologies

paper_content:

A deadlock-free tree-based multicast routing algorithm is presented for all direct networks, regardless of interconnection topology. The algorithm delivers a message to any number of destinations using only a single start up phase. In contrast to existing tree-based schemes, this algorithm applies to all interconnection topologies, requires only fixed-sized input buffers that are independent of maximum message length, and uses a simple asynchronous flit replication mechanism. The theoretical basis of the technique used here is sufficiently general to develop other tree-based multicasting algorithms for regular and irregular topologies. Simulation results demonstrate that this tree-based algorithm provides a very promising means of achieving very low latency multicast.
---
paper_title: Note on packing of edge-disjoint spanning trees in sparse random graphs

paper_content:

The \emph{spanning tree packing number} of a graph $G$ is the maximum number of edge-disjoint spanning trees contained in $G$. Let $k\geq 1$ be a fixed integer. Palmer and Spencer proved that in almost every random graph process, the hitting time for having $k$ edge-disjoint spanning trees equals the hitting time for having minimum degree $k$. In this paper, we prove that for any $p$ such that $(\log n+\omega(1))/n\leq p\leq (1.1\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is equal to the minimum degree. Note that this bound for $p$ will allow the minimum degree to be a function of $n$, and in this sense we improve the result of Palmer and Spencer. Moreover, we also obtain that for any $p$ such that $p\geq (51\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is less than the minimum degree.
---
paper_title: Graphs with Large Generalized (Edge-)Connectivity

paper_content:

Let G be a graph, and S a set of vertices of G. Denote by λ(S) the maximum number l of pairwise edge-disjoint trees T1,T2,··· ,Tl in G such that V (Ti) ⊇ S for every 1 ≤ i ≤ l. Then the generalized k-edge-connectivity λk(G) of G is defined as λk(G) = min{λ(S)|S ⊆ V (G) and |S| = k}. Thus λ2(G) = λ(G). In this paper, sharp upper and lower bounds of λ3(G) are given for a connected graph G of order n, that is, 1 ≤ λ3(G) ≤ n − 2. Graphs of order n such that λ3(G) = n − 2, n − 3 are characterized, respectively.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: Path-connectivity in graphs

paper_content:

Abstract We call a graph G ( k , n )-path-connected iff for any subset A of the vertex set of G with cardinality k there exist n edge-disjoint paths P i , 1⩽ i ⩽ n , which contain A and are vertex-disjoint with the exception of A . This is a specialization of the tree-connectivity introduced in a previous article. We give necessary and sufficient conditions for a graph to be ( k,n )-path-connected proving that κ ( G )⩾2 κ −2 n implies the ( k,n )-path-connectivity of G and ( k −1) n is a lower bound for this implication. For the cases k =2,3,4 we show that this lower bound is also sufficient.
---
paper_title: The generalized 3-connectivity of random graphs

paper_content:

The generalized connectivity of a graph $G$ was introduced by Chartrand et al. Let $S$ be a nonempty set of vertices of $G$, and $\kappa(S)$ be defined as the largest number of internally disjoint trees $T_1, T_2, \cdots, T_k$ connecting $S$ in $G$. Then for an integer $r$ with $2 \leq r \leq n$, the {\it generalized $r$-connectivity} $\kappa_r(G)$ of $G$ is the minimum $\kappa(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $\kappa_2(G)=\kappa(G)$, is the vertex connectivity of $G$, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let $\lambda(S)$ denote the largest number $k$ of pairwise edge-disjoint trees $T_1, T_2, \ldots, T_k$ connecting $S$ in $G$. Then the {\it generalized $r$-edge-connectivity} $\lambda_r(G)$ of $G$ is defined as the minimum $\lambda(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $\lambda_2(G) = \lambda(G)$. ::: In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer $k\geq 1$, $$p=\frac{{\log n+(k+1)\log \log n -\log \log \log n}}{n}$$ is a sharp threshold function for the property $\kappa_3(G(n, p)) \geq k$, which could be seen as a counterpart of Bollob\'{a}s and Thomason's result for vertex connectivity. Moreover, we obtain that $\delta (G(n,p)) - 1 = \lambda (G(n,p)) - 1 = \kappa (G(n,p)) - 1 \le {\kappa_3}(G(n,p)) \le {\lambda_3}(G(n,p)) \le \kappa (G(n,p)) = \lambda (G(n,p)) = \delta (G(n,p))$ almost surely holds, which could be seen as a counterpart of Ivchenko's result.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: Topics in Structural Graph Theory

paper_content:

Foreword Ortrud R. Oellermann Preface Lowell W. Beineke and Robin J. Wilson Preliminaries Lowell W. Beineke and Robin J. Wilson 1. Menger's theorem Ortrud R. Oellermann 2. Maximally connected graphs Dirk Meierling and Lutz Volkmann 3. Minimal connectivity Matthias Kriesell 4. Contractions of k-connected graphs Kiyoshi Ando 5. Connectivity and cycles R. J. Faudree 6. H-linked graphs Michael Ferrara and Ronald J. Gould 7. Tree-width and graph minors Dieter Rautenbach and Bruce Reed 8. Toughness and binding numbers Ian Anderson 9. Graph fragmentability Keith Edwards and Graham Farr 10. The phase transition in random graphs Bela Bollobas and Oliver Riordan 11. Network reliability and synthesis F. T. Boesch, A. Satyanarayana and C. L. Suffel 12. Connectivity algorithms Abdol-Hossein Esfahanian 13. Using graphs to find the best block designs R. A. Bailey and Peter J. Cameron Notes on contributors Index.
---
paper_title: The average connectivity of a graph

paper_content:

In this paper, we consider the concept of the average connectivity of a graph, defining it to be the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. Our main results are sharp bounds on the value of this parameter, and a construction of graphs whose average connectivity is the same as the connectivity. Along the way, we establish some new results on connectivity.
---
paper_title: A Generalization of Line Connectivity and Optimally Invulnerable Graphs

paper_content:

In this work we explore the properties of a simple generalization of $\lambda $, the line connectivity of a graph. This parameter designated by $\lambda _i $ is defined as the minimum number of lines which must be removed from a graph in order that the number of resulting components is greater than i. Several properties of $\lambda _i $ are derived, and the problem of finding graphs which are optimal with respect to $\lambda _i $ is discussed.
---
paper_title: The generalized 3-edge-connectivity of lexicographic product graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and GBH the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any two connected graphs G and H, κ3(G^H)≥ κ3(G)|V(H)|. We also give upper bounds for κ3(GB H) and κ3(G^H). Moreover, all the bounds are sharp.
---
paper_title: Edge-disjoint trees containing some given vertices in a graph

paper_content:

We show that for any two natural numbers k, l there exist (smallest natural numbers fl(k)(gl(k)) such that for any fl(k)-edge-connected (gl(k)-edge-connected) vertex set A of a graph G with |A| ≤ l(|V(G) - A| ≤ l) there exists a system J of k edge-disjoint trees such that A ⊆ V(T) for each T ∈ J. We determine f3(k) = ⌊ 8k+3/6 ⌋. Furthermore, we determine for all natural numbers l,k the smallest number fl*(k) such that every fl*(k)-edge-connected graph on at most l vertices contains a system of k edge-disjoint spanning trees, and give applications to line graphs.
---
paper_title: Fractional arboricity, strength, and principal partitions in graphs and matroids

paper_content:

Abstract In a 1983 paper, D. Gusfield introduced a function which is called (following W.H. Cunningham, 1985) the strength of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link, this is the function η(G) = minF⊆E(G) ∣F∣/(ω(G − F) − ω(G)), where the minimum is taken over all subsets F of E(G) such that ω(G − F), the number of components of G − F, is at least ω(G) + 1. In a 1986 paper, C. Payan introduced the fractional arboricity of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link this function is γ(G) = maxH⊆G ∣E(H)∣/(∣V(H)∣ − ω(H)), where H runs over all subgraphs of G having at least one link. Connected graphs G for which γ(G) = η(G) were used by A. Rucinski and A. Vince in 1986 while studying random graphs. We characterize the graphs and matroids G for which γ(G) = η(G). The values of γ and η are computed for certain graphs, and a recent result of Erdos (that if each edge of G lies in a C3, then ∣E(G)∣≥ 3 2 (∣V(G)∣ − 1)) is generalized in terms of η. The principal partition of a graph was introduced in 1967 by G. Kishi and Y. Kajitani, by T. Ohtsuki, Y. Ishizaki, and H. Watanabe, and by M. Iri (all of these were published in 1968). It has been used since then for the analysis of electrical networks in which the two Kirchhoff laws and Ohm's law hold, because it often allows the currents and voltage drops in the network to be completely computed with fewer measurements than are required for either of the Kirchhoff laws used alone. J. Bruno and L. Weinberg generalized the principal partition to matroids in 1971, and their generalization was refined independently by N. Tomizawa (1976) and by H. Narayanan and M.N. Vartak (1974, 1981). Here we demonstrate that γ and η are closely related to the principal partition and can be used to give a simple definition of both the principal partition and the more recent refinements of it.
---
paper_title: Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results

paper_content:

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.
---
paper_title: Steiner Trees in Industry

paper_content:

The following problems are worth studying: ::: ::: ::: Open problems on the Steiner ratio, such as Chung-Gilbert’s conjecture, Graham-Hwang’s conjecture, and Cielick’s conjecture, etc.. ::: ::: ::: Find better approximation for network Steiner trees and establish an explicit lower bound for the approximation performance ratio of network Steiner trees. ::: ::: ::: Close the gap between the lower bound and the upper bound for the approximation performance ratio of Steiner minimum arborescence. ::: ::: ::: Find more efficient approximation algorithms for on-line and dynamic Steiner minimum trees and various Steiner tree packing problems. ::: ::: ::: Find good approximation algorithms for multi-weighted Steiner trees and multiphase Steiner trees and study close relationship between multi-weighted Steiner trees, multiphase Steiner trees, and phylogenetic trees. ::: ::: ::: Make clear whether there exists a polynomial-time approximation scheme for class Steiner tree in the special case with the real world background and highway interconnection problem. ::: ::: ::: Close the gap between the lower bound and the upper bound for the approximation performance ratio of bottleneck Steiner tree in the Euclidean plane and make clear whether there exists a polynomial-time approximation scheme for the Steiner tree with minimum number of Steiner points and bounded edge-length. ::: ::: ::: Implement efficient approximation algorithms to meet the requests from industries.
---
paper_title: Toughness in graphs a survey

paper_content:

In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!
---
paper_title: Steiner Tree Problems in Computer Communication Networks

paper_content:

The Steiner tree problem is one of the most important combinatorial optimization problems. It has a long history that can be traced back to the famous mathematician Fermat (1601 1665). This book studies three significant breakthroughs on the Steiner tree problem that were achieved in the 1990s, and some important applications of Steiner tree problems in computer communication networks researched in the past fifteen years. It not only covers some of the most recent developments in Steiner tree problems, but also discusses various combinatorial optimization methods, thus providing a balance between theory and practice. Contents: Minimax Approach and Steiner Ratio; k-Steiner Ratios and Better Approximation Algorithms; Geometric Partitions and Polynomial Time Approximation Schemes; Grade of Service Steiner Tree Problem; Steiner Tree Problem for Minimal Steiner Points; Bottleneck Steiner Tree Problem; Steiner k-Tree and k-Path Routing Problems; Steiner Tree Coloring Problem; Steiner Tree Scheduling Problem; Survivable Steiner Network Problem.
---
paper_title: Edge-disjoint trees containing some given vertices in a graph

paper_content:

We show that for any two natural numbers k, l there exist (smallest natural numbers fl(k)(gl(k)) such that for any fl(k)-edge-connected (gl(k)-edge-connected) vertex set A of a graph G with |A| ≤ l(|V(G) - A| ≤ l) there exists a system J of k edge-disjoint trees such that A ⊆ V(T) for each T ∈ J. We determine f3(k) = ⌊ 8k+3/6 ⌋. Furthermore, we determine for all natural numbers l,k the smallest number fl*(k) such that every fl*(k)-edge-connected graph on at most l vertices contains a system of k edge-disjoint spanning trees, and give applications to line graphs.
---
paper_title: Edge disjoint Steiner trees in graphs without large bridges

paper_content:

A set A of vertices of an undirected graph G is called k-edge-connected in G if for all pairs of distinct vertices a, b∈A, there exist k edge disjoint a, b-paths in G. An A-tree is a subtree of G containing A, and an A-bridge is a subgraph B of G which is either formed by a single edge with both end vertices in A or formed by the set of edges incident with the vertices of some component of G - A. It is proved that (i) if A is k·(e + 2)-edge-connected in G and every A-bridge has at most e vertices in V(G) - A or at most e + 2 vertices in A then there exist k edge disjoint A-trees, and that (ii) if A is k-edge-connected in G and B is an A-bridge such that B is a tree and every vertex in V(B) - A has degree 3 then either A is k-edge-connected in G - e for some e∈E(B) or A is (k - 1)-edge-connected in G - E(B). © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 188–198, 2009
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: An approximate max-Steiner-tree-packing min-Steiner-cut theorem

paper_content:

Given an undirected multigraph G and a subset of vertices S /spl sube/ V(G), the Steiner tree packing problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme unless P=NP). In fact, prior to this paper, not even an approximation algorithm with asymptotic ratio o(n) was known despite several attempts. In this work, we close this huge gap by presenting the first polynomial time constant factor approximation algorithm for the Steiner tree packing problem. The main theorem is an approximate min-max relation between the maximum number of edge-disjoint trees that each connects S (i.e. S-trees) and the minimum size of an edge-cut that disconnects some pair of vertices in S (i.e. S-cut). Specifically, we prove that if the minimum S-cut in G has 26k edges, then G has at least k edge-disjoint S-trees; this answers Kriesell's conjecture affirmatively up to a constant multiple. The techniques that we use are purely combinatorial, where matroid theory is the underlying ground work.
---
paper_title: Packing Steiner trees

paper_content:

The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph G that connect a given set of required points S. This problem is motivated by practical applications in VLSI- layout and broadcasting, as well as theoretical reasons. In this paper, we study this problem and present an algorithm with an asymptotic approximation factor of vSv/4. This gives a sufficient condition for the existence of k edge-disjoint Steiner trees in a graph in terms of the edge-connectivity of the graph. We will show that this condition is the best possible if the number of terminals is 3. At the end, we consider the fractional version of this problem, and observe that it can be reduced to the minimum Steiner tree problem via the ellipsoid algorithm.
---
paper_title: Optimal attack and reinforcement of a network

paper_content:

In a nonnegative edge-weighted network, the weight of an edge represents the effort required by an attacker to destroy the edge, and the attacker derives a benefit for each new component created by destroying edges. The attacker may want to minimize over subsets of edges the difference between (or the ratio of) the effort incurred and the benefit received. This idea leads to the definition of the “strength” of the network, a measure of the resistance of the network to such attacks. Efficient algorithms for the optimal attack problem, the problem of computing the strength, and the problem of finding a minimum cost “reinforcement” to achieve a desired strength are given. These problems are also solved for a different model, in which the attacker wants to separate vertices from a fixed central vertex.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: Edge-disjoint trees containing some given vertices in a graph

paper_content:

We show that for any two natural numbers k, l there exist (smallest natural numbers fl(k)(gl(k)) such that for any fl(k)-edge-connected (gl(k)-edge-connected) vertex set A of a graph G with |A| ≤ l(|V(G) - A| ≤ l) there exists a system J of k edge-disjoint trees such that A ⊆ V(T) for each T ∈ J. We determine f3(k) = ⌊ 8k+3/6 ⌋. Furthermore, we determine for all natural numbers l,k the smallest number fl*(k) such that every fl*(k)-edge-connected graph on at most l vertices contains a system of k edge-disjoint spanning trees, and give applications to line graphs.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: Graphs with Large Generalized (Edge-)Connectivity

paper_content:

Let G be a graph, and S a set of vertices of G. Denote by λ(S) the maximum number l of pairwise edge-disjoint trees T1,T2,··· ,Tl in G such that V (Ti) ⊇ S for every 1 ≤ i ≤ l. Then the generalized k-edge-connectivity λk(G) of G is defined as λk(G) = min{λ(S)|S ⊆ V (G) and |S| = k}. Thus λ2(G) = λ(G). In this paper, sharp upper and lower bounds of λ3(G) are given for a connected graph G of order n, that is, 1 ≤ λ3(G) ≤ n − 2. Graphs of order n such that λ3(G) = n − 2, n − 3 are characterized, respectively.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: A survey of Nordhaus-Gaddum type relations

paper_content:

In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the order of the graph. Since then, relations of a similar type have been proposed for many other graph invariants, in several hundred papers. We present a survey on this research endeavor.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: THE MAXIMUM CONNECTIVITY OF A GRAPH

paper_content:

Abstract : The paper solves the problem of the maximum connectivity of any graph with a given number of points and lines. In addition, the minimum connectivity. The maximum diameter, and the minimum diameter are obtained. Two unsolved problems concerning the distribution of the values of the connectivity and the diameter are included.
---
paper_title: Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

paper_content:

For a graph G and a set S of vertices of G , let λ ( S ) denote the maximum number ? of pairwise edge-disjoint Steiner trees T 1 , T 2 , ? , T ? in G such that S ? V ( T i ) for every 1 ? i ? ? . For an integer k with 2 ? k ? n , where n is the order of G , the generalized k -edge-connectivity λ k ( G ) of G is defined as λ k ( G ) = min { λ ( S ) ? S ? V ( G ) a n d | S | = k } . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λ k ( G ) . We obtain sharp upper and lower bounds of λ k ( G ) + λ k ( G ? ) and λ k ( G ) ? λ k ( G ? ) for a graph G of order n , as well as a graph G of order n and size m . Some graph classes attaining these bounds are also given.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: The cross product of interconnection networks

paper_content:

We study the cross product as a method for generating and analyzing interconnection network topologies for multiprocessor systems. Consider two interconnection graphs G/sub 1/ and G/sub 2/ each with some established properties such as symmetry, low degree and diameter, scalability, simple optimal routing, recursive structure (partitionability), fault tolerance, existence of node-disjoint paths, low cost embedding, and efficient broadcasting. We investigate and evaluate the corresponding properties for the cross product of G/sub 1/ and G/sub 2/ based on the properties of G/sub 1/ and those of G/sub 2/. We also give a mathematical characterization of product families of graphs which are closed under the cross product operation. This investigation is useful in two ways. On one hand, it gives a new tool for further studying some of the known interconnection topologies, such as the hypercube and the mesh, which can be defined using the cross product operation. On the other hand, it can be used in defining and evaluating new interconnection graphs using the cross product operation on known topologies.
---
paper_title: Reliable Broadcasting in Product Networks

paper_content:

Abstract We investigate the reliability of broadcasting in product networks containing faulty nodes and/or links. Faults considered in this paper are mainly of the Byzantine type, i.e., a faulty node or a faulty link may not only stop sending a message but also arbitrarily change a message passing through the faulty place or even fabricate a false message. We assume that no nodes have a priori information about faults in a network. Hence, the key problem of reliable broadcasting in our model is how to control the message transmission so that any corrupted message cannot affect the result of the broadcasting too much. We propose the concept of an n-channel graph which has n-independent spanning trees rooted at each node. The fault tolerance can be achieved by sending n copies of the message along the n-independent spanning trees rooted at the source node. In this paper we show how to construct n-independent spanning trees of a product network from spanning trees of n-component graphs. Furthermore, we can design an efficient and reliable broadcasting scheme based on independent spanning trees for a product network from simple broadcasting schemes for component networks. The degrees of fault tolerance against crash faults and Byzantine faults of nodes and/or links are, respectively, n − 1 and ⌊(n − 1)/2⌋ in the worst case. We can successfully broadcast with a probability higher than 1 − k −⌈ n 2 ⌉ in any product network of order N consisting of n-component graphs of order b or less, if at most N/4b3nk faulty nodes are randomly distributed in the network. We can also successfully broadcast with a probability higher than 1 − k −⌈ n 2 ⌉ in any product network of size L, of n component graphs of size b or less, if at most L l2b 2 k faulty links are randomly distributed in the network.
---
paper_title: Connectivity of Cartesian products of graphs

paper_content:

Abstract Let κ ( G ) be the connectivity of G and G □ H the Cartesian product of G and H . We prove that for any nontrivial graphs G and H , κ ( G □ H ) = min { κ ( G ) | H | , κ ( H ) | G | , δ ( G □ H ) } .
---
paper_title: Handbook of Product Graphs

paper_content:

A BRIEF INTRODUCTION TO GRAPHS AND THEIR PRODUCTS Graphs Graphs and Subgraphs Paths and Cycles Trees and Forests Planar Graphs Automorphisms and Invariants Automorphisms Vertex-Transitivity Graph Invariants The No-Homomorphism Lemma Hypercubes and Isometric Subgraphs Hypercubes are Sparse Isometric Subgraphs Median Graphs Retracts Graph Products Three Fundamental Products Commutativity, Associativity, and Multiple Factors Projections and Layers Classification of Products The Four Standard Graph Products The Cartesian Product The Strong Product The Direct Product The Lexicographic Product FACTORIZATION AND CANCELLATION Cartesian Product Prime Factor Decompositions Cartesian Product and Its Group Transitive Group Action on Products Cancellation S-Prime Graphs Strong Product Basic Properties and S-Thin Graphs Cliques and the Extraction of Complete Factors Unique Prime Factorization for Connected Graphs Automorphisms Direct Product Nonuniqueness of Prime Factorization R-Thin Graphs The Cartesian Skeleton Factoring Connected, Nonbipartite, R-Thin Graphs Factoring Connected, Nonbipartite Graphs Automorphisms Applications to the Strong Product Cancellation Cancellation for the Strong Product Cancellation for the Direct Product Anti-Automorphisms and Factorials Graph Exponentiation Lexicographic Product Basic Properties Self-Complementarity and Cancellation Properties Commutativity Factorizations and Nonuniqueness Automorphisms ISOMETRIC EMBEDDINGS The Relation THETA and Partial Cubes Definition and Basic Properties of THETA Characterizations of Partial Cubes Cubic Partial Cubes Scale Embeddings into Hypercubes Median Graphs Mulder's Convex Expansion Inequalities for Median Graphs and Partial Cubes Median Graphs as Retracts A Fixed Cube Theorem Median Networks in Human Genetics The Canonical Isometric Embedding The Embedding and Its Properties The Relation THETA and the Cartesian Product Automorphisms of Canonical Embeddings A Dynamic Location Problem Hamming Graphs Graphs with Finite Windex Quasi-Median Graphs and Generalizations Graphs with Finite Windex are Quasi-Median Graphs Isometries in Strong Products and Product Dimensions Strong Isometric Dimension Retracts of Strong Products Other Product Graph Dimensions Fixed Box Theorems Gated Subgraphs and Median Functions A Fixed Box Theorem for Median Function-Closed Graphs Feder-Tardif's Fixed Box Theorems Fixed Points of Several Nonexpansive Mappings ALGORITHMS Graph Representation and Algorithms Time and Space Complexity Adjacency List Breadth-First Search Adjacency Matrix Recognizing Hypercubes and Partial Cubes Hypercubes Partial Cubes Efficient Computation of THETA* Recognizing Partial Cubes in Quadratic Time Chemical Graphs and the Wiener Index Benzenoid Graphs as Partial Cubes The Wiener Index of Benzenoid Graphs in Linear Time The Wiener Index via the Canonical Isometric Embedding Arboricity, Squares, and Triangles Arboricity Listing Squares and Triangles Recognizing Median Graphs A Simple Algorithm A Fast Algorithm Triangle-Free Graphs and Median Graphs Recognizing Partial Hamming Graphs and Quasi-Median Graphs Hamming Graphs and Partial Hamming Graphs Quasi-Median Graphs Computing the Windex Factoring the Cartesian Product Product Relation A Simple Algorithm Coordinatization Factorization in O(m log n) Time Factorization in Linear Time and Space Recognizing Direct, Strong, and Lexicographic Products Direct Product Strong Product Factoring Thin Graphs Factoring Non-Thin Graphs Lexicographic Product INVARIANTS Connectivity Cartesian Product Critically Connected Graphs and the Lexicographic Product Strong and Direct Products Coloring and Hedetniemi's Conjecture Product Coloring Bounds and Three Applications Fractional and Circular Chromatic Number Hedetniemi's Conjecture Hedetniemi's Conjecture for 4-Chromatic Graphs Circular and Fractional Version of Hedetniemi's Conjecture Independence Number and Shannon Capacity Shannon Capacity Independence in Direct Products Independence in Cartesian Products Domination and Vizing's Conjecture Vizing's Conjecture Clark and Suen's Approach Fractional Version of Vizing's Conjecture Domination in Direct Products Cycle Spaces and Bases The Cycle Space of a Graph Minimum Cycle Bases for Cartesian and Strong Products Minimum Cycle Bases for the Lexicographic Product Minimum Cycle Bases for the Direct Product Selected Results One-Factorization and Edge-Coloring Hamilton Cycles and Hamiltonian Decompositions Clique Minors in Cartesian Products Reconstruction, Topological Embeddings, and Flows Modeling Complex Networks RELATED CONCEPTS Infinite Graphs Growth Rate and Ends Free Product Transitive Median Graphs with Finite Blocks Two-Ended Median Graphs Cartesian Product Strong and Direct Product Lexicographic Product Products of Digraphs Definitions Connectedness Tournaments and the Lexicographic Product Prime Factorings Cancellation Near Products Graph Bundles Approximate Graph Products Graph Spectra Zig-Zag Product Appendix: Hints and Solutions to Exercises Bibliography Author Index Subject Index Symbol Index
---
paper_title: Lower bounds for the spanning tree numbers of two graph products

paper_content:

For any graph $G$ of order $n$, the spanning tree packing number \emph{$STP(G)$}, is the maximum number of edge-disjoint spanning trees contained in $G$. In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs.
---
paper_title: Identifying codes of lexicographic product of graphs

paper_content:

Gravier et al. investigated the identifying codes of Cartesian product of two graphs. In this paper we consider the identifying codes of lexicographic product G[H] of a connected graph G and an arbitrary graph H, and obtain the minimum cardinality of identifying codes of G[H] in terms of some parameters of G and H.
---
paper_title: The generalized 3-connectivity of Lexicographic product graphs

paper_content:

The generalized $k$-edge-connectivity $\lambda_k(G)$ of a graph $G$ is a generalization of the concept of edge-connectivity. The lexicographic product of two graphs $G$ and $H$, denoted by $G\circ H$, is an important graph product. In this paper, we mainly study the generalized 3-edge-connectivity of $G \circ H$, and get upper and lower bounds of $\lambda_3(G \circ H)$. Moreover, all bounds are sharp.
---
paper_title: Handbook of Product Graphs

paper_content:

A BRIEF INTRODUCTION TO GRAPHS AND THEIR PRODUCTS Graphs Graphs and Subgraphs Paths and Cycles Trees and Forests Planar Graphs Automorphisms and Invariants Automorphisms Vertex-Transitivity Graph Invariants The No-Homomorphism Lemma Hypercubes and Isometric Subgraphs Hypercubes are Sparse Isometric Subgraphs Median Graphs Retracts Graph Products Three Fundamental Products Commutativity, Associativity, and Multiple Factors Projections and Layers Classification of Products The Four Standard Graph Products The Cartesian Product The Strong Product The Direct Product The Lexicographic Product FACTORIZATION AND CANCELLATION Cartesian Product Prime Factor Decompositions Cartesian Product and Its Group Transitive Group Action on Products Cancellation S-Prime Graphs Strong Product Basic Properties and S-Thin Graphs Cliques and the Extraction of Complete Factors Unique Prime Factorization for Connected Graphs Automorphisms Direct Product Nonuniqueness of Prime Factorization R-Thin Graphs The Cartesian Skeleton Factoring Connected, Nonbipartite, R-Thin Graphs Factoring Connected, Nonbipartite Graphs Automorphisms Applications to the Strong Product Cancellation Cancellation for the Strong Product Cancellation for the Direct Product Anti-Automorphisms and Factorials Graph Exponentiation Lexicographic Product Basic Properties Self-Complementarity and Cancellation Properties Commutativity Factorizations and Nonuniqueness Automorphisms ISOMETRIC EMBEDDINGS The Relation THETA and Partial Cubes Definition and Basic Properties of THETA Characterizations of Partial Cubes Cubic Partial Cubes Scale Embeddings into Hypercubes Median Graphs Mulder's Convex Expansion Inequalities for Median Graphs and Partial Cubes Median Graphs as Retracts A Fixed Cube Theorem Median Networks in Human Genetics The Canonical Isometric Embedding The Embedding and Its Properties The Relation THETA and the Cartesian Product Automorphisms of Canonical Embeddings A Dynamic Location Problem Hamming Graphs Graphs with Finite Windex Quasi-Median Graphs and Generalizations Graphs with Finite Windex are Quasi-Median Graphs Isometries in Strong Products and Product Dimensions Strong Isometric Dimension Retracts of Strong Products Other Product Graph Dimensions Fixed Box Theorems Gated Subgraphs and Median Functions A Fixed Box Theorem for Median Function-Closed Graphs Feder-Tardif's Fixed Box Theorems Fixed Points of Several Nonexpansive Mappings ALGORITHMS Graph Representation and Algorithms Time and Space Complexity Adjacency List Breadth-First Search Adjacency Matrix Recognizing Hypercubes and Partial Cubes Hypercubes Partial Cubes Efficient Computation of THETA* Recognizing Partial Cubes in Quadratic Time Chemical Graphs and the Wiener Index Benzenoid Graphs as Partial Cubes The Wiener Index of Benzenoid Graphs in Linear Time The Wiener Index via the Canonical Isometric Embedding Arboricity, Squares, and Triangles Arboricity Listing Squares and Triangles Recognizing Median Graphs A Simple Algorithm A Fast Algorithm Triangle-Free Graphs and Median Graphs Recognizing Partial Hamming Graphs and Quasi-Median Graphs Hamming Graphs and Partial Hamming Graphs Quasi-Median Graphs Computing the Windex Factoring the Cartesian Product Product Relation A Simple Algorithm Coordinatization Factorization in O(m log n) Time Factorization in Linear Time and Space Recognizing Direct, Strong, and Lexicographic Products Direct Product Strong Product Factoring Thin Graphs Factoring Non-Thin Graphs Lexicographic Product INVARIANTS Connectivity Cartesian Product Critically Connected Graphs and the Lexicographic Product Strong and Direct Products Coloring and Hedetniemi's Conjecture Product Coloring Bounds and Three Applications Fractional and Circular Chromatic Number Hedetniemi's Conjecture Hedetniemi's Conjecture for 4-Chromatic Graphs Circular and Fractional Version of Hedetniemi's Conjecture Independence Number and Shannon Capacity Shannon Capacity Independence in Direct Products Independence in Cartesian Products Domination and Vizing's Conjecture Vizing's Conjecture Clark and Suen's Approach Fractional Version of Vizing's Conjecture Domination in Direct Products Cycle Spaces and Bases The Cycle Space of a Graph Minimum Cycle Bases for Cartesian and Strong Products Minimum Cycle Bases for the Lexicographic Product Minimum Cycle Bases for the Direct Product Selected Results One-Factorization and Edge-Coloring Hamilton Cycles and Hamiltonian Decompositions Clique Minors in Cartesian Products Reconstruction, Topological Embeddings, and Flows Modeling Complex Networks RELATED CONCEPTS Infinite Graphs Growth Rate and Ends Free Product Transitive Median Graphs with Finite Blocks Two-Ended Median Graphs Cartesian Product Strong and Direct Product Lexicographic Product Products of Digraphs Definitions Connectedness Tournaments and the Lexicographic Product Prime Factorings Cancellation Near Products Graph Bundles Approximate Graph Products Graph Spectra Zig-Zag Product Appendix: Hints and Solutions to Exercises Bibliography Author Index Subject Index Symbol Index
---
paper_title: Lexicographic Products and the Power of Non-linear Network Coding

paper_content:

We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding problems. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hyper graph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that this is a valid dual solution of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.
---
paper_title: The generalized 3-edge-connectivity of lexicographic product graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and GBH the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any two connected graphs G and H, κ3(G^H)≥ κ3(G)|V(H)|. We also give upper bounds for κ3(GB H) and κ3(G^H). Moreover, all the bounds are sharp.
---
paper_title: On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

paper_content:

The problem of determining the smallest number of edges, $h(n;\bar{\kappa}\geq r)$, which guarantees that any graph with $n$ vertices and $h(n;\bar{\kappa}\geq r)$ edges will contain a pair of vertices joined by $r$ internally disjoint paths was posed by Erd\"{o}s and Gallai. Bollob\'{a}s considered the problem of determining the largest number of edges $f(n;\bar{\kappa}\leq \ell)$ for graphs with $n$ vertices and local connectivity at most $\ell$. One can see that $f(n;\bar{\kappa}\leq \ell)= h(n;\bar{\kappa}\geq \ell+1)-1$. These two problems had received a wide attention of many researchers in the last few decades. In the above problems, only pairs of vertices connected by internally disjoint paths are considered. In this paper, we study the number of internally disjoint Steiner trees connecting sets of vertices with cardinality at least 3.
---
paper_title: On k-Rails in Graphs

paper_content:

A k-rail is the union of k paths each pair of which has exactly the endvertices in common. We first give a sufficient degree-condition for the existence of k-rails in graphs. Next we determine the number of edges required in 3-connected graphs to guarantee the existence of 5-rails, and finally we solve the corresponding problem for graphs with no prescribed connectivity.
---
paper_title: On the generalized (edge-)connectivity of graphs

paper_content:

The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.
---
paper_title: On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

paper_content:

The concept of maximum local connectivity $\bar {\kappa}$ of a graph was introduced by Bollob\'{a}s. One of the problems about it is to determine the largest number of edges $f(n;\bar{\kappa}\leq \ell)$ for graphs of order $n$ that have local connectivity at most $\ell$. We consider a generalization of the above concept and problem. For $S\subseteq V(G)$ and $|S|\geq 2$, the \emph{generalized local connectivity} $\kappa(S)$ is the maximum number of internally disjoint trees connecting $S$ in $G$. The parameter $\bar{\kappa}_k(G)=max\{\kappa(S)|S\subseteq V(G),|S|=k\}$ is called the \emph{maximum generalized local connectivity} of $G$. This paper it to consider the problem of determining the largest number $f(n;\bar{\kappa}_k\leq \ell)$ of edges for graphs of order $n$ that have maximum generalized local connectivity at most $\ell$. The exact value of $f(n;\bar{\kappa}_k\leq \ell)$ for $k=n,n-1$ is determined. For a general $k$, we construct a graph to obtain a sharp lower bound.
---
paper_title: On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

paper_content:

The concept of maximum local connectivity $\bar {\kappa}$ of a graph was introduced by Bollob\'{a}s. One of the problems about it is to determine the largest number of edges $f(n;\bar{\kappa}\leq \ell)$ for graphs of order $n$ that have local connectivity at most $\ell$. We consider a generalization of the above concept and problem. For $S\subseteq V(G)$ and $|S|\geq 2$, the \emph{generalized local connectivity} $\kappa(S)$ is the maximum number of internally disjoint trees connecting $S$ in $G$. The parameter $\bar{\kappa}_k(G)=max\{\kappa(S)|S\subseteq V(G),|S|=k\}$ is called the \emph{maximum generalized local connectivity} of $G$. This paper it to consider the problem of determining the largest number $f(n;\bar{\kappa}_k\leq \ell)$ of edges for graphs of order $n$ that have maximum generalized local connectivity at most $\ell$. The exact value of $f(n;\bar{\kappa}_k\leq \ell)$ for $k=n,n-1$ is determined. For a general $k$, we construct a graph to obtain a sharp lower bound.
---
paper_title: Arboricity and spanning-tree packing of random graphs

paper_content:

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph G (n, p). For all p(n) ∈ [0, 1], we show that, with high probability, T is precisely the minimum between δ and bm/(n − 1)c, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals bm/(n−1)c and A equals dm/(n−1)e; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k →∞.
---
paper_title: Hitting time fork edge-disjoint spanning trees in a random graph

paper_content:

We show that in almost every random graph process, the hitting time for havingk edge-disjoint spanning trees equals the hitting time for having minimum degreek.
---
paper_title: Note on packing of edge-disjoint spanning trees in sparse random graphs

paper_content:

The \emph{spanning tree packing number} of a graph $G$ is the maximum number of edge-disjoint spanning trees contained in $G$. Let $k\geq 1$ be a fixed integer. Palmer and Spencer proved that in almost every random graph process, the hitting time for having $k$ edge-disjoint spanning trees equals the hitting time for having minimum degree $k$. In this paper, we prove that for any $p$ such that $(\log n+\omega(1))/n\leq p\leq (1.1\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is equal to the minimum degree. Note that this bound for $p$ will allow the minimum degree to be a function of $n$, and in this sense we improve the result of Palmer and Spencer. Moreover, we also obtain that for any $p$ such that $p\geq (51\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is less than the minimum degree.
---
paper_title: Edge disjoint spanning trees in random graphs

paper_content:

We show that almost every G . contains m edge disjoint spanning m—out trees. Introduction In this note we consider the maximum number of edge disjoint spanning trees contained in the random graph G _ . Let a graph G = (V,E) have property sL if it contains spanning trees T1tTo,...,T, which are pair-wise edge disjoint. We consider the random graph G = G . This has vertex set V = m m-out n {l,2,...,n}. Each v € V independently chooses a set out(v) of distinct vertices as neighbours, where each m-subset of V -{v} is equally likely to be chosen. This produces a random m out-regular diagraph D which has m been selected uniformly from ( ) distinct possibilities. G is obtained by ignoring orientation but without coalescing edges. (See [1], [2], [3] for properties of this model.) Probability statements refer to the probability space of D and graph theoretic statements refer to G . m Theorem 1 Let m > 2 be a fixed constant. Then lim Pr(G € st ) = 1. I n^> m m [This is clearly best possible.] The major graph theoretic result underpinning our proof is as follows. University Libraries "arnegie Mellon University rtfh.PA f5213-3890 Theorem 2 (Nash-Williams [5], Tutte [6]) A graph G = (V,E) has property sL if and only if for every partition SlfSo,...,S of V, 2 < t < |v|, there at least k(t-l) edges of G joining vertices in different subsets of the partition. D (The necessity of the condition is obvious. The "meat" is in the sufficiency.) Proof of main result For S C V let -Y(S) = |{vw € E(D ): v € S, w CS} I. "~ n m
---
paper_title: Random Graphs of Small Order

paper_content:

Our aim in this paper is to present results about random graphs with fairly few vertices. In addition to theoretical results, many of which are obtained by substantial use of a computer, we present a large number of tables displaying the parameters of various randomly chosen graphs of small order.
---
paper_title: The generalized 3-connectivity of random graphs

paper_content:

The generalized connectivity of a graph $G$ was introduced by Chartrand et al. Let $S$ be a nonempty set of vertices of $G$, and $\kappa(S)$ be defined as the largest number of internally disjoint trees $T_1, T_2, \cdots, T_k$ connecting $S$ in $G$. Then for an integer $r$ with $2 \leq r \leq n$, the {\it generalized $r$-connectivity} $\kappa_r(G)$ of $G$ is the minimum $\kappa(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $\kappa_2(G)=\kappa(G)$, is the vertex connectivity of $G$, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let $\lambda(S)$ denote the largest number $k$ of pairwise edge-disjoint trees $T_1, T_2, \ldots, T_k$ connecting $S$ in $G$. Then the {\it generalized $r$-edge-connectivity} $\lambda_r(G)$ of $G$ is defined as the minimum $\lambda(S)$ where $S$ runs over all the $r$-subsets of the vertex set of $G$. Obviously, $\lambda_2(G) = \lambda(G)$. ::: In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer $k\geq 1$, $$p=\frac{{\log n+(k+1)\log \log n -\log \log \log n}}{n}$$ is a sharp threshold function for the property $\kappa_3(G(n, p)) \geq k$, which could be seen as a counterpart of Bollob\'{a}s and Thomason's result for vertex connectivity. Moreover, we obtain that $\delta (G(n,p)) - 1 = \lambda (G(n,p)) - 1 = \kappa (G(n,p)) - 1 \le {\kappa_3}(G(n,p)) \le {\lambda_3}(G(n,p)) \le \kappa (G(n,p)) = \lambda (G(n,p)) = \delta (G(n,p))$ almost surely holds, which could be seen as a counterpart of Ivchenko's result.
---

Title: A Survey on the Generalized Connectivity of Graphs

Section 1: Introduction
Description 1: In this section, we provide both theoretical and practical motivation for introducing the concept of generalized (edge-)connectivity of graphs. Key definitions in graph theory are also given.

Section 2: Motivation and definition
Description 2: This section delves into the basic concepts of connectivity, including classical definitions and their generalizations. It explains why classical connectivity and edge-connectivity fall short in practical applications, leading to the introduction of generalized connectivities.

Section 3: Notation and terminology
Description 3: Here, we present the notation and terminology used throughout the survey, ensuring that readers are familiar with the graph theoretical language and symbols utilized in subsequent sections.

Section 4: Results for some graph classes
Description 4: This section outlines specific results related to the generalized connectivity of various graph classes, such as complete multipartite graphs, complete bipartite graphs, and others. It also includes important theorems and conjectures in this area.

Section 5: Algorithm and complexity
Description 5: This section discusses the computational complexity of determining generalized connectivity. It explores polynomial-time algorithms, NP-completeness results, and approximation algorithms for calculating generalized connectivity parameters.

Section 6: Sharp bounds for the generalized connectivity
Description 6: In this section, we provide sharp upper and lower bounds for generalized connectivity parameters. We discuss the significance of these bounds and present examples of graphs that attain them.

Section 7: Graphs with large generalized connectivity
Description 7: This section investigates graphs that achieve the maximum generalized connectivity values. It includes characterizations of such graphs and provides conjectures for their critical properties.

Section 8: Nordhaus-Gaddum-type results
Description 8: Here, we explore Nordhaus-Gaddum-type relations for generalized connectivity. This section includes theoretical results and characterizations of extremal graphs.

Section 9: Results for graph operations
Description 9: This section surveys the effects of various graph operations—such as line graphs and graph products—on generalized connectivity. Important results, lower bounds, and upper bounds are provided for these operations.

Section 10: Extremal problems
Description 10: This section focuses on extremal problems related to generalized connectivity and generalized edge-connectivity. It includes results on the minimal size of graphs with given connectivity parameters and the maximum generalized local connectivity.

Section 11: For random graphs
Description 11: This section surveys results on the generalized connectivity of random graphs. It includes threshold functions, sharp threshold results, and distributions for generalized connectivity in random graph models.

Section 12: An application problem
Description 12: Here, we present an application problem related to network reliability and security. The problem involves finding a minimal network with desired generalized connectivity properties and characterizes graphs that solve it.