Name
Abstract | ||
|---|---|---|
Assume that G is a triangle-free graph. Let be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε.
|
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/s004930050035 | Combinatorica |
Keywords | Field | DocType |
connected graph,maximum degree | Graph,Discrete mathematics,Combinatorics,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
18 | 4 | 0209-9683 |
Citations | PageRank | References |
14 | 1.25 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Erdös | 1 | 43 | 6.19 |
| András Gyárfás | 2 | 582 | 102.26 |
| M. Ruszinkó | 3 | 230 | 35.16 |