𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximum degree and diameter-bounded subgraph in the mesh

✍ Scribed by Mirka Miller; Hebert Pérez-Rosés; Joe Ryan

Book ID
113564831
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
264 KB
Volume
160
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An ILP formulation and genetic algorithm
An ILP formulation and genetic algorithm for the Maximum Degree-Bounded Connected Subgraph problem
✍ Milena Bogdanović 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 344 KB

A general instance of a Degree-Constrained Subgraph problem may be found in an edgeweighted or vertex-weighted graph G whereas the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This class of combinatorial problems has been e

Forbidden subgraphs and bounds on the si
Forbidden subgraphs and bounds on the size of a maximum matching
✍ Michael D. Plummer; Akira Saito 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let __K__~1,__n__~ denote the star on __n__ + 1 vertices; that is, __K__~1,__n__~ is the complete bipartite graph having one vertex in the first vertex class of its bipartition and __n__ in the second. The special graph __K__~1,3~, called the __claw__, has received much attention in the

The maximum number of edges in 2K2-free
The maximum number of edges in 2K2-free graphs of bounded degree
✍ F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.