Arbitrarily regularizable graphs

DOI10.24166/IM.10.2017zbMATH Open1491.05183arXiv1608.06427OpenAlexW2963919960MaRDI QIDQ3389691FDOQ3389691

Authors: Enrico Bozzo, Massimo Franceschet 

Publication date: 23 March 2022

Published in: Internet Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1608.06427

Recommendations

• scientific article; zbMATH DE number 2188467
• Net regular signed trees
• scientific article; zbMATH DE number 3887746
• scientific article; zbMATH DE number 3843805
• Inducing regulation of any digraphs

zbMATH Keywords

signed networksgraph regularizabilitymatrix chainabilitypower in networks

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Matrix Analysis
• Concerning nonnegative matrices and doubly stochastic matrices
• Networks, crowds and markets. Reasoning about a highly connected world.
• Matching theory
• Social and economic networks.
• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• The Distribution of Positive Elements in Doubly-Stochastic Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs and matrices
• A fast algorithm for matrix balancing
• Convex Sets of Non-Negative Matrices
• Fair Majority Voting (or How to Eliminate Gerrymandering)
• On the existence of sequences and matrices with prescribed partial sums of elements
• Problems Involving Diagonal Products in Nonnegative Matrices
• The chainable matrix, a special combinatorial matrix
• Patterns that allow given row and column sums
• Regularisable graphs, II
• Patterns, linesums, and symmetry

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Arbitrarily regularizable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3389691)