Arbitrarily regularizable graphs

DOI10.24166/IM.10.2017MaRDI QIDQ3389691zbMATH OpenOpenAlexFDO

Authors Enrico Bozzo, Massimo Franceschet

Publication date 23 March 2022

Published in Internet Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(1)

• scientific article; zbMATH DE number 3843805 (Why is no real title available?)

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)