We show that for a certain class of convex functions f , including the exponential functions x ↦ e λ x with λ > 0 a real number, and all the powers x ↦ x β , x ≥ 0 and β ≥ 2 a real number, with a unique small exception, if ( d 1 , … , d n ) ranges over the degree sequences of graphs with n vertices and m edges and m ≤ n − 1 , then the maximum of ∑ i f ( d i ) is uniquely attained by the degree sequence of a quasi-star graph, namely, a graph consisting of a star plus possibly additional isolated vertices. This result significantly extends a similar result in Ismailescu and Stefanica (2002). Dually, we show that for a certain class of concave functions g , including the negative exponential functions x ↦ 1 − e − λ x with λ > ln ( 2 ) a real number, all the powers x ↦ x α , x ≥ 0 and 0 < α ≤ 1 2 a real number, and the function x ↦ x x + 1 for x ≥ 0 , if ( d 1 , … , d n ) ranges over the degree sequences of graphs with n vertices and m edges, then the minimum of ∑ i g ( d i ) is uniquely attained by the degree sequence of a quasi-complete graph, i.e., a graph consisting of a complete graph plus possibly an additional vertex connected to some but not all vertices of the complete graph, plus possibly isolated vertices. This result extends a similar result in the same paper.

SUMMARY: It has been observed in different kinds of networks, such as social or biological ones, a typical behavior inspired by the general principle 'similarity breeds connections'. These networks are defined as homophilic as nodes belonging to the same class preferentially interact with each other. In this work, we present HONTO (HOmophily Network TOol), a user-friendly open-source Python3 package designed to evaluate and analyze homophily in complex networks. The tool takes in input from the network along with a partition of its nodes into classes and yields a matrix whose entries are the homophily/heterophily z-score values. To complement the analysis, the tool also provides z-score values of nodes that do not interact with any other node of the same class. Homophily/heterophily z-scores values are presented as a heatmap allowing a visual at-a-glance interpretation of results. AVAILABILITY AND IMPLEMENTATION: Tool's source code is available at https://github.com/cumbof/honto under the MIT license, installable as a package from PyPI (pip install honto) and conda-forge (conda install -c conda-forge honto), and has a wrapper for the Galaxy platform available on the official Galaxy ToolShed (Blankenberg et al., 2014) at https://toolshed.g2.bx.psu.edu/view/fabio/honto.

A $\{0,1\}$-matrix $\mathsf{A}$ is balanced if it does not contain a submatrix of odd order having exactly two 1's per row and per column. A graph is balanced if its clique-matrix is balanced. No characterization of minimally unbalanced graphs is known, and even no conjecture on the structure of such graphs has been posed, contrary to what happened for perfect graphs. In this paper, we provide such a characterization for the class of diamond-free graphs and establish a connection between minimally unbalanced diamond-free graphs and Dyck-paths.

Given a simple undirected graph $G$ and a positive integer $s$, the maximum vertex coverage problem (MVC) is the problem of finding a set $U$ of $s$ vertices of $G$ such that the number of edges having at least one endpoint in $U$ is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37--48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv:1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a $4/5$-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC.

We provide a polynomial algorithm that determines for any given undirected graph $G=(V,E)$, positive integer k, and convex functions $f_v:\mathbb{N}\rightarrow\mathbb{R}$ ($v\in V$) a subgraph $H=(V,F)$ of k edges that minimizes $\sum_{v\in V}f_v(d_H(v))$, where $d_H(v)$ is the degree of v in H. The motivation and at the same time the main application of the results is the problem of finding a subset of k vertices in a line graph that covers as many edges as possible. The latter problem generalizes the vertex cover problem for line graphs, which is in turn equivalent to the maximum matching problem in graphs. Improving paths or walks for factorization problems have to be completed by pairs of such walks for this problem. We provide several solutions leading to different variants of the problem and also show the limits of the methods by proving the NP-completeness of some direct extensions, in particular to all convex functions.

Abstract This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit‐center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP‐hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract In this article we continue our study on the complexity of Path Covering Problems started in 2 . Here, taking one further step, we investigate the complexity of the problem on grids. For special classes of grids (general grids, grids with a fixed number of rows, ladders), and several special unweighted path collections (general paths, paths of length 2, L‐shaped paths, pipes, hooks, staples) we either give polynomial‐time algorithms or prove NP‐completeness results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 120–131 2004