Name
Title | ||
|---|---|---|
Variable Neighborhood Search For Extremal Graphs. 9. Bounding The Irregularity Of A Graph |
Abstract | ||
|---|---|---|
Albertson [1] defines the imbalance of an edge (i,j) epsilon E of a graph G = (V, E) as vertical bar d(i) - d(j)vertical bar where d(j) is the degree of a vertex j epsilon V, and the irregularity irr(G) of G as the sum of imbalances of its edges. Exploiting conjectures of the system AutoGraphiX, an upper bound on irr(G) is derived, which is tight for all numbers n = vertical bar V vertical bar and m = vertical bar E vertical bar of vertices and edges compatible with the existence of a graph:irr(G) <= d(n - d)(n - d + 1) + t(t - 2d - 1)whered = [n - 1/2 - root((n- 1/2)(2) - 2m)]andt = m - (n - d)d - d(d - 1)/2.Extremal graphs are shown to be fanned split graphs, i.e., complete split graphs with the possible addition of edges all incident with the same vertex. |
Year | Venue | Keywords |
|---|---|---|
2001 | GRAPHS AND DISCOVERY | graph, conjecture, irregularity, computer-assisted system, automated system |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Variable neighborhood search,Extremal graph theory,Mathematics,Bounding overwatch | Conference | 69 |
ISSN | Citations | PageRank |
1052-1798 | 16 | 1.19 |
References | Authors | |
2 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierre Hansen | 1 | 1538 | 135.51 |
| Hadrien Melot | 2 | 95 | 14.02 |