Abstract | ||
---|---|---|
Let G be a graph. The irregularity index of G, denoted by t(G), is the number of distinct values in the degree sequence of G. For any graph G, t(G) ≤ Δ(G), where Δ(G) is the maximum degree. If t(G) = Δ(G), then G is called maximally irregular. In this paper, we give a tight upper bound on the size of maximally irregular graphs, and prove the conjecture proposed in [6] on the size of maximally irregular triangle-free graphs. Extremal graphs are also characterized. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/s00373-013-1304-1 | Graphs and Combinatorics |
Keywords | Field | DocType |
maximally irregular triangle-free graph,maximally irregular graphs,extremal graph,maximum degree,degree sequence,maximally irregular graph,distinct value,maximally irregular triangle-free graphs,graph g,irregularity index,maximally irregular | Graph,Topology,Discrete mathematics,Combinatorics,Indifference graph,Upper and lower bounds,Chordal graph,Degree (graph theory),Pathwidth,Conjecture,Triangle-free graph,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 3 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fengxia Liu | 1 | 0 | 2.70 |
Zhao Zhang | 2 | 706 | 102.46 |
Jixiang Meng | 3 | 353 | 55.62 |