FUTUR. Website for the scientific production of UPC researchers.

The p-restricted edge-connectivity of Kneser graphs

Author: Balbuena, C.; Marcote, F.

Type of activity: Journal article
Journal: Applied mathematics and computation
Date of publication: 2019-02-15
Volume: 343
First page: 258
Last page: 267
DOI: 10.1016/j.amc.2018.09.072

Repository: http://hdl.handle.net/2117/184872
https://www.researchgate.net/publication/330060412_The_p-restricted_edge-connectivity_of_Kneser_graphs
URL: https://www.sciencedirect.com/science/article/abs/pii/S0096300318308592?via%3Dihub
Abstract: Given a connected graph G and an integer 1¿=¿p¿=¿¿|V(G)|/2¿, a p-restricted edge-cut of G is any set of edges S¿¿¿E(G), if any, such that is not connected and each component of has at least p vertices; and the p-restricted edge-connectivity of G, denoted ¿p(G), is the minimum cardinality of such a p-restricted edge-cut. When p-restricted edge-cuts exist, G is said to be super-¿p if the deletion from G of any p-restricted edge-cut S of cardinality ¿p(G) yields a graph that has at leas...

Given a connected graph G and an integer 1¿=¿p¿=¿¿|V(G)|/2¿, a p-restricted edge-cut of G is any set of edges S¿¿¿E(G), if any, such that is not connected and each component of has at least p vertices; and the p-restricted edge-connectivity of G, denoted ¿p(G), is the minimum cardinality of such a p-restricted edge-cut. When p-restricted edge-cuts exist, G is said to be super-¿p if the deletion from G of any p-restricted edge-cut S of cardinality ¿p(G) yields a graph that has at least one component with exactly p vertices. In this work, we prove that Kneser graphs K(n, k) are ¿p-connected for a wide range of values of p. Moreover, we obtain the values of ¿p(G) for all possible p and all n¿=¿5 when . Also, we discuss in which cases ¿p(G) attains its maximum possible value, and determine for which values of p graph is super-¿p. © 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Citation: Balbuena, C.; Marcote, F. The p-restricted edge-connectivity of Kneser graphs. "Applied mathematics and computation", 15 Febrer 2019, vol. 343, p. 258-267.
Keywords: Kneser graphs, Restricted edge connectivity

Group of research: COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

Balbuena Martinez, Maria Camino Teofila (author)
Marcote Ordax, Francisco Javier (author)

Attachments

AMC-RestrictedEdgeKneser.pdf (477982 bytes)