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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1120360
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact