Document Type : Research Paper

Author

• Bahareh Bafandeh Mayvan

Department of Computer Engineering, Ferdowsi University of Mashhad

Abstract

The edge tenacity T_e(G) of a graph G is dened as:
T_e(G) = min {[|X|+τ(G-X)]/[ω(G-X)-1]|X ⊆ E(G) and ω(G-X) > 1}
where the minimum is taken over every edge-cutset X that separates G into ω(G - X) components, and by τ(G - X) we denote the order of a largest component of G. The objective of this paper is to determine this quantity for split graphs. Let G = (Z; I; E) be a noncomplete connected split graph with minimum vertex degree δ(G) we prove that if δ(G)≥|E(G)|/[|V(G)|-1]  then its edge-tenacity is |E(G)|/[|V(G)|-1] .

Keywords

• Vertex degree
• split graphs
• edge tenacity