On the sizes of graphs and their powers: The undirected case |
| |
| Authors: | David Auger Antoine Lobstein |
| |
| Affiliation: | a Institut Telecom - Telecom ParisTech & Centre National de la Recherche Scientifique - LTCI UMR 5141, 46, rue Barrault, 75634 Paris Cedex 13, Franceb Centre National de la Recherche Scientifique - LTCI UMR 5141 & Telecom ParisTech, 46, rue Barrault, 75634 Paris Cedex 13, France |
| |
| Abstract: | ![]()
Let G be an undirected graph and Gr be its r-th power. We study different issues dealing with the number of edges in G and Gr. In particular, we answer the following question: given an integer r≥2 and all connected graphs G of order n such that Gr≠Kn, what is the minimum number of edges that are added when going from G to Gr, and which are the graphs achieving this bound? |
| |
| Keywords: | Graph theory Undirected graph Diameter Power of a graph Transitive closure of a graph Edge number Size of a graph Identifying code Hamiltonian graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
