Extreme tenacity of graphs with given order and size

DOI10.1007/S40305-014-0052-0MaRDI QIDQ489128zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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\)

Cites work

• scientific article; zbMATH DE number 2186976 (Why is no real title available?)
• scientific article; zbMATH DE number 989237 (Why is no real title available?)
• scientific article; zbMATH DE number 4043858 (Why is no real title available?)
• scientific article; zbMATH DE number 4053662 (Why is no real title available?)
• scientific article; zbMATH DE number 1885936 (Why is no real title available?)
• scientific article; zbMATH DE number 861347 (Why is no real title available?)
• scientific article; zbMATH DE number 867714 (Why is no real title available?)
• A large class of maximally tough graphs
• Connectivity and edge-disjoint spanning trees
• Edge‐tenacious networks
• Graph theory with applications
• Minimum integrity of graphs
• On a class of posets and the corresponding comparability graphs
• Rupture degree of graphs
• Some maximally tough circulants.
• THE MAXIMUM CONNECTIVITY OF A GRAPH
• Tenacity of complete graph products and grids
• Tough graphs and Hamiltonian circuits.

Cited in

(12)

• On the first-order edge tenacity of a graph
• scientific article; zbMATH DE number 5139491 (Why is no real title available?)
• Tenacity and the maximum network
• Computing the tenacity of some graphs
• The weak hyperedge tenacity of the hypercycles
• 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 of total graphs
• Tenacity and rupture degree of permutation graphs of complete bipartite graphs
• Computing tenacity, rupture degree and some other vulnerability parameters in polynomial time for classes of intersection 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)