×

On the spanning fan-connectivity of graphs. (English) Zbl 1183.05045

Summary: Let \(G\) be a graph. The connectivity of \(G\), \(\kappa(G)\), is the maximum integer \(k\) such that there exists a \(k\)-container between any two different vertices. A \(k\)-container of \(G\) between \(u\) and \(v\), \(C_k(u,v)\), is a set of \(k\)-internally-disjoint paths between \(u\) and \(v\). A spanning container is a container that spans \(V(G)\). A graph \(G\) is \(k^*\)-connected if there exists a spanning \(k\)-container between any two different vertices. The spanning connectivity of \(G\), \(\kappa^*(G)\), is the maximum integer \(k\) such that \(G\) is \(w^*\)-connected for \(1\leq w\leq k\) if \(G\) is \(1^*\)-connected.
Let \(x\) be a vertex in \(G\) and let \(U=\{y_1,y_2,\dots,y_k\}\) be a subset of \(V(G)\) where \(x\) is not in \(U\). A spanning \(k-(x,U)\)-fan, \(F_k(x,U)\), is a set of internally-disjoint paths \(\{P_1,P_2,\dots,P_k\}\) such that \(P_i\) is a path connecting \(x\) to \(y_i\) for \(1\leq i\leq k\) and \(\bigcup^k_{i=1}V(P_i)=V(G)\). A graph \(G\) is \(k^*\)-fan-connected (or \(k^*_j\)-connected) if there exists a spanning \(F_k(x,U)\)-fan for every choice of \(x\) and \(U\) with \(|U|=k\) and \(x\neq U\). The spanning fan-connectivity of a graph \(G\), \(\kappa^*_f(G)\), is defined as the largest integer \(k\) such that \(G\) is \(w^*_f\)-connected for \(1\leq w\leq k\) if \(G\) is \(1^*_f\)-connected.
In this paper, some relationship between \(\kappa(G)\), \(\kappa^*(G)\), and \(\kappa_f^*(G)\) are discussed. Moreover, some sufficient conditions for a graph to be \(\kappa_f^*\)-connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be \(k^*\)-pipeline-connected.

MSC:

05C40 Connectivity
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1980), North Holland: North Holland New York · Zbl 1134.05001
[2] Hsu, D. F., On container width and length in graphs, groups, and networks, IEICE Transactions Fundamentals, E77-A, 668-680 (1994)
[3] Menger, K., Zur allgemeinen kurventheorie, Fundamentale Mathematik, 10, 95-115 (1927) · JFM 53.0561.01
[4] Albert, M.; Aldred, R. E.L.; Holton, D., On \(3^\ast \)-connected graphs, Australasian Journal of Combinatorics, 24, 193-208 (2001) · Zbl 0982.05062
[5] Hsu, H.-C.; Lin, C.-K.; Hung, H.-M.; Hsu, L.-H., The spanning connectivity of the \((n, k)\)-star graphs, International Journal of Foundations of Computer Science, 17, 415-434 (2006) · Zbl 1103.68097
[6] Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., The super connectivity of the pancake graphs and star graphs, Theoretical Computer Science, 339, 257-271 (2005) · Zbl 1074.05054
[7] Lin, C.-K.; Huang, H.-M.; Hsu, D. F.; Hsu, L.-H., The spanning diameter of the star graph, Networks, 48, 235-249 (2006) · Zbl 1107.05055
[8] Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., On the spanning connectivity of graphs, Discrete Mathematics, 307, 285-289 (2007) · Zbl 1177.05064
[9] Lin, C.-K.; Huang, H.-M.; Tan, J. J.M.; Hsu, L.-H., On spanning connected graphs, Discrete Mathematics, 308, 1330-1333 (2008) · Zbl 1134.05045
[10] Tsai, C.-H.; Tan, J. J.M.; Hsu, L.-H., The super connected property of recursive circulant graphs, Information Processing Letters, 91, 293-298 (2004) · Zbl 1177.68031
[11] Dirac, G. A., In abstrakten Graphen vorhandene vollstäandige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten, 22, 61-85 (1960) · Zbl 0096.17903
[12] Dirac, G. A., Some theorem on abstract graphs, Proceedings of the London Mathematical Society, 2, 69-81 (1952) · Zbl 0047.17001
[13] Ore, O., Note on Hamilton circuits, American Mathematical Monthly, 67, 55 (1960) · Zbl 0089.39505
[14] Ore, O., Hamiltonian connected graphs, Journal of Mathematic Pures Application, 42, 21-27 (1963) · Zbl 0106.37103
[15] Bondy, J. A.; Chvátal, V., A method in graph theory, Discrete Mathematic, 15, 111-135 (1976) · Zbl 0331.05138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.