WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 15, 2016
Restricted Edge Connectivity and Restricted Connectivity of Graphs
Authors: ,
Abstract: Let $$G = (V, E)$$ be a connected graph. Let $$G = (V, E)$$ be a connected graph. An edge set $$F ⊂ E$$ is said to be a $$k-restricted$$ edge cut, if $$G − F$$ is disconnected and every component of $$G − F$$ has at least $$k$$ vertices. The $$k-restricted$$ edge connectivity of $$G$$ denoted by $$λ_{k}(G)$$, is the cardinality of a minimum $$k-restricted$$ edge cut of $$G$$. A graph $$G$$ is $$λ_{k}-connected$$, if $$G$$ contains a $$k-restricted$$ edge cut. A $$λ_{k}-connected$$ graph $$G$$ is called $$λ_{k}-optimal$$, if $$λ_{k}(G) = ξ_{k}(G)$$, where $$ξ_{k}(G)= \left \{ |[U, V − U]| : U ⊂ V, |U| = k \space and \space G[U] \space is \space connected \right \}$$. An vertex set $$X$$ is a $$k-restricted$$ cut of $$G$$, if $$G − X$$ is not connected and every component of $$G − X$$ has at least k vertices. The $$k-restricted$$ connectivity $$κ_{k}(G)$$ (in short $$κ_{k}$$) of $$G$$, is the cardinality of a minimum $$k-restricted$$ cut of $$G$$. A $$λ_{k}-connected$$ graph $$G$$ is said to be $$super-λ_{k}$$, if $$G$$ is $$λ_{k}-optimal$$ and every minimum $$k-restricted$$ edge cut isolates a component with exactly $$k$$ vertices. A $$κ_{k}-connected$$ graph $$G$$ is said to be $$super-κ_{k}$$, if $$κ_{3}(G) = ξ_{3}(G)$$ and the deletion of each minimum $$k-restricted$$ cut isolates a component with exactly $$k$$ vertices. In this paper, we study the restricted edge connectivity and restricted connectivity of graphs, line graphs and a kind of transformation graphs.
Search Articles
Pages: 441-449
WSEAS Transactions on Mathematics, ISSN / E-ISSN: 1109-2769 / 2224-2880, Volume 15, 2016, Art. #41