| |
| An edge is subverted if the two ends of the edge aredeleted from the graph. The edge-neighbor-connectivity$lambda_{NB}(G)$ is the minimum number of edges the subversion ofwhich results in an empty, or trivial, or disconnected graph. It isknown that $lambda_{NB}(G)leqlfloor n/2
floor$, where$n=|V(G)|$. In this paper, we characterize all extremal graphs whoseedge-neighbor-connectivity reaches this upper bound: for even $n$,an extremal graph can only be the complete graph $K_n$ or thecomplete bipartite graph $K_{ rac{n}{2}, rac{n}{2}}$; for odd $n$,an extremal graph can only be the 5-cycle $C_5$, or $K_n-M_0$ (thecomplete graph with a matching $M_0$ removed, where $M_0$ is anarbitrary matching of $K_n$ containing $i$ edges for $iin{0,1,ldots,lfloor n/2
floor}$), or a graph $G$ spanned by a$K_{lfloor rac{n}{2}
floor,lceil rac{n}{2}
ceil}$ such thatthe $lfloor n/2
floor$-part is independent in $G$ and the subgraphinduced by the $lceil n/2
ceil$-part has matching number at mostone. |
|
| Keywords:graph theory, edge-neighbor-connectivity, extremal graph. |
|
