A graph is regularizable if it is possible to assign weights to its edges so that all nodes have the same degree. Weights can be positive, nonnegative or arbitrary as soon as the regularization degree is not null. Positive and nonnegative regularizable graphs have been thoroughly investigated in the literature. In this work, we propose and study arbitrarily regularizable graphs. In particular, we investigate necessary and sufficient regularization conditions on the topology of the graph and of the corresponding adjacency matrix. Moreover, we study the computational complexity of the regularization problem and characterize it as a linear programming model.
Arbitrarily regularizable graphs
FRANCESCHET, Massimo;BOZZO, Enrico
2017-01-01
Abstract
A graph is regularizable if it is possible to assign weights to its edges so that all nodes have the same degree. Weights can be positive, nonnegative or arbitrary as soon as the regularization degree is not null. Positive and nonnegative regularizable graphs have been thoroughly investigated in the literature. In this work, we propose and study arbitrarily regularizable graphs. In particular, we investigate necessary and sufficient regularization conditions on the topology of the graph and of the corresponding adjacency matrix. Moreover, we study the computational complexity of the regularization problem and characterize it as a linear programming model.File | Dimensione | Formato | |
---|---|---|---|
main.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
301.13 kB
Formato
Adobe PDF
|
301.13 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.