Generalized graph entropies

This article deals with generalized entropies for graphs. These entropies result from applying information measures to a graph using various schemes for defining probability distributions over the elements (e.g., vertices) of the graph. We introduce a new class of generalized measures, develop their properties, compute the measures for selected graphs, and briefly discuss potential applications to classification and clustering problems. © 2011 Wiley Periodicals, Inc. Complexity, 17,45–50, 2011     

On the Laplacian energy of a graph

In this paper we consider the energy of a simple graph with respect to its Laplacian eigenvalues, and prove some basic properties of this energy. In particular, we find the minimal value of this energy in the class of all connected graphs on n vertices (n = 1, 2, ...). Besides, we consider the class of all connected graphs whose Laplacian energy is uniformly bounded by a constant α ⩾ 4, and completely describe this class in the case α = 40.     

Some relations between Hausdorff-dimensions and entropies

Some relations between the Hausdorff-dimensions and the entropies for expansive homeomorphisms on compact metric spaces are obtained. Project partially supported by the National Natural Science Foundation of China.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

On the Laplacian spectrum of an infinite graph

In this paper, we introduce the notion of Laplacian spectrum of an infinite countable graph in a different way than in the papers by B. Mohar. We prove some basic properties of this type of spectrum. The approach used is in line with our approach to the limiting spectrum of an infinite graph. The technique of the Laplacian spectrum of finite graphs is essential in this approach.     

A case study of cracks in the scientific enterprise: Reinvention of information‐theoretic measures for graphs

This article calls attention to flaws in the scientific enterprise, providing a case study of the lack of professionalism in published journal articles in a particular area of research, namely, network complexity. By offering details of a special case of poor scholarship, which is very likely indicative of a broader problem, the authors hope to stimulate editors and referees to greater vigilance, and to strengthen authors' resolve to take their professional responsibilities more seriously. © 2014 Wiley Periodicals, Inc. Complexity 21: 10–14, 2016     

A generalization of Fiedler's lemma and some applications

In a previous paper [M. Robbiano, E.A. Martins, and I. Gutman, Extending a theorem by Fiedler and applications to graph energy, MATCH Commun. Math. Comput. Chem. 64 (2010), pp. 145–156], a lemma by Fiedler was used to obtain eigenspaces of graphs, and applied to graph energy. In this article Fiedler's lemma is generalized and this generalization is applied to graph spectra and graph energy.     

A unique graph of minimal elastic energy

Nonlinear functionals that appear as a product of two integrals are considered in the context of elastic curves of variable length. A technique is introduced that exploits the fact that one of the integrals has an integrand independent of the derivative of the unknown. Both the linear and the nonlinear cases are illustrated. By lengthening parameterized curves it is possible to reduce the elastic energy to zero. It is shown here that for graphs this is not the case. Specifically, there is a unique graph of minimal elastic energy among all graphs that have turned 90 degrees after traversing one unit.

     

On the total variation distance between the binomial random graph and the random intersection graph

When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph and the Erdös‐Rényi graph tends to 0 for any if , where is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any whenever .     

Connections between generalized,inexact and semi-infinite linear programming

This paper presents duality results between generalized and inexact linear programs and describes a special type of linear semi-infinite programs in connection with the programs above mentioned. In order to solve inexact linear programs a corresponding auxiliary problem can be formulated which is explicitly solvable. However, this auxiliary problem is a reformulation of the reduced semi-infinite problem. Therefore, all the numerical methods for solving semi-infinite linear programs can be used for the numerical treatment of inexact and generalized linear programs.

---

Zusammenfassung Die vorliegende Arbeit zeigt Dualitätsergebnisse zwischen verallgemeinerten und inexakten linearen Programmen auf und beschreibt einen speziellen Typ linear-semi-infiniter Programme in Zusammenhang mit den oben erwähnten Optimierungsaufgaben. Um inexakte lineare Programme zu lösen wird ein Hilfsproblem aufgestellt, das explizit lösbar ist. Dieses Hilfsproblem ist eine Reformulierung des reduzierten semi-infiniten Problems. Daher können alle numerischen Methoden zur Lösung semi-infiniter linearer Programme auch zur numerischen Behandlung von inexakten und verallgemeinerten lineraren Programmen herangezogen werden.

     

Making an H $H$-free graph k $k$-colorable

We study the following question: How few edges can we delete from any $H$-free graph on $n$ vertices to make the resulting graph $k$-colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For $H$ any fixed odd cycle, we determine the answer up to a constant factor when $n$ is sufficiently large. We also prove an upper bound when $H$ is a fixed clique that we conjecture is tight up to a constant factor, and prove upper bounds for more general families of graphs. We apply our results to get a new bound on the maximum cut of graphs with a forbidden odd cycle in terms of the number of edges.     

信息量和熵的关系

介绍了信息量和熵,它们分别是信息科学和热力学中的概念,但是在实际应用中却有着十分紧密的联系,它们影响着人们对事物的发展变化进行的判断和决策.讨论了它们的关系,以及在具体实例中的应用.     

Relation between the H-rank of a mixed graph and the rank of its underlying graph

Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $\stackrel{?}{G}$ is obtained from $G$ by orienting some of its edges. Let $H\left(\stackrel{?}{G}\right)$ denote the Hermitian adjacency matrix of $\stackrel{?}{G}$ and $A\left(G\right)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $\stackrel{?}{G}$ (resp. $G$), written as $rk\left(\stackrel{?}{G}\right)$ (resp. $r\left(G\right)$), is the rank of $H\left(\stackrel{?}{G}\right)$ (resp. $A\left(G\right)$). Denote by $d\left(G\right)$ the dimension of cycle space of $G$, that is $d\left(G\right)=\left|E_G\right|?\left|V_G\right|+\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $\stackrel{?}{G}$ and the rank of $G$. We first show that $?2d\left(G\right)?rk\left(\stackrel{?}{G}\right)?r\left(G\right)?2d\left(G\right)$ for every mixed graph $\stackrel{?}{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently.     

On the approximation of Laplacian eigenvalues in graph disaggregation

Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple small-degree vertices, in order to allow for more efficient computation in parallel. In particular, we consider computations involving the graph Laplacian, which has significant applications, including diffusion mapping and graph partitioning, among others. We prove results regarding the spectral approximation of the Laplacian of the original graph by the Laplacian of the disaggregated graph. In addition, we construct an alternate disaggregation operator whose eigenvalues interlace those of the original Laplacian. Using this alternate operator, we construct a uniform preconditioner for the original graph Laplacian.