Extreme tenacity of graphs with given order and size

DOI10.1007/S40305-014-0052-0zbMATH Open1306.90026arXiv1109.4673OpenAlexW2039617196MaRDI QIDQ489128FDOQ489128

Authors: Yinkui Li, Chuandong Xu, T. C. Edwin Cheng, Shenggui Zhang 

Publication date: 27 January 2015

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Abstract: Computer or communication networks are so designed that they do not easily get disrupted under external attack and, moreover, these are easily reconstructible if they do get disrupted. These desirable properties of networks can be measured by various graph parameters, such as connectivity, toughness, scattering number, integrity, tenacity, rupture degree and edge-analogues of some of them. Among these parameters, the tenacity and rupture degree are two better ones to measure the stability of a network. In this paper we consider two extremal problems on the tenacity of graphs: Determine the minimum and maximum tenacity of graphs with given order and size. We give a complete solution to the first problem, while for the second one, it turns out that the problem is much more complicated than that of the minimum case. We determine the maximum tenacity of trees and unicyclic graphs with given order and show the corresponding extremal graphs. These results are helpful in constructing stable networks with lower costs. The paper concludes with a discussion of a related problem on the edge vulnerability parameters of graphs.

Full work available at URL: https://arxiv.org/abs/1109.4673

Recommendations

• Computing the tenacity of some graphs
• Tenacity-maximum graphs
• Tenacity and rupture degree of permutation graphs of complete bipartite graphs
• scientific article; zbMATH DE number 2197993
• On networks with maximum graphical structure and tenacity \(T\)

zbMATH Keywords

treesmaximum tenacityminimum tenacityvulnerability parameters

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Reliability, availability, maintenance, inspection in operations research (90B25) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Communication networks in operations research (90B18)

Cites Work

• Tenacity of complete graph products and grids
• Graph theory with applications
• Edge‐tenacious networks
• Title not available (Why is that?)
• Tough graphs and Hamiltonian circuits.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a class of posets and the corresponding comparability graphs
• THE MAXIMUM CONNECTIVITY OF A GRAPH
• Rupture degree of graphs
• Title not available (Why is that?)
• A large class of maximally tough graphs
• Connectivity and edge-disjoint spanning trees
• Title not available (Why is that?)
• Some maximally tough circulants.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum integrity of graphs

Cited In (10)

• On the first-order edge tenacity of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tenacity and the maximum network
• Computing the tenacity of some graphs
• A note on ``Tenacity of a graph with maximum connectivity
• Tenacity-maximum graphs
• On networks with maximum graphical structure and tenacity \(T\)
• Tenacity of complete graph products and grids
• Tenacity and rupture degree of permutation graphs of complete bipartite graphs

This page was built for publication: Extreme tenacity of graphs with given order and size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489128)