Minimizer graphs for a class of extremal problems | Zendy

Ismailescu Dan | Zendy; Stefanica Dan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Minimizer graphs for a class of extremal problems

Author(s) -

Ismailescu Dan,

Stefanica Dan

Publication year - 2002

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.10025

Subject(s) - combinatorics , mathematics , vertex (graph theory) , chordal graph , graph , discrete mathematics , induced subgraph

We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research