Let G be a graph with adjacency matrix A(G) and let D(G) be the diagonal matrix of the degrees of G. For any real α∈0,1, Nikiforov (2017) 7 defined the matrix Aα(G) as Aα(G)=αD(G)+(1−α)A(G). Let u ...and v be two vertices of a connected graph G. Suppose that u and v are connected by a path w0(=v)w1⋯ws−1ws(=u) where d(wi)=2 for 1≤i≤s−1. Let Gp,s,q(u,v) be the graph obtained by attaching the paths Pp to u and Pq to v. Let s=0,1. Nikiforov and Rojo (2018) 9 conjectured that ρα(Gp,s,q(u,v))<ρα(Gp−1,s,q+1(u,v)) if p≥q+2. In this paper, we confirm the conjecture. As applications, firstly, the extremal graph with maximal Aα-spectral radius with fixed order and cut vertices is characterized. Secondly, we characterize the extremal tree which attains the maximal Aα-spectral radius with fixed order and matching number. These results generalize some known results.
Influence maximization problem is an important issue in social network analysis, the diversity of social network structure has continuously injected vitality into the influence maximization problem, ...which has been a hot issue in academic circles for nearly two decades. The research on the existing problem of influence maximization mainly focuses on the characteristics of the node, and rarely considers the influence maximization problem from the perspective of social networks connectivity. As a bridge between connected components, the cut-vertex is the core of connectivity. To this end, this paper comprehensively considers the characteristics of node and connectivity of social networks, and proposes a heuristic algorithm based on cut-vertex to solve the influence maximization problem. The algorithm uses degree and connected components to evaluate the influence of nodes, which solves the problem of overlapping influences to a certain extent. Based on the susceptible-infected-recovered model, this paper conducts
The partial Hosoya polynomial (or briefly the partial H-polynomial) can be used to construct the well-known Hosoya polynomial. The ith coefficient of this polynomial, defined for an arbitrary vertex ...u of a graph G, is the number of vertices at distance i from u. The aim of this paper is to determine the partial H-polynomial of several well-known graphs and, then, to investigate the location of their zeros. To pursue, we characterize the structure of graphs with the minimum and the maximum modulus of the zeros of partial H-polynomial. Finally, we define another graph polynomial of the partial H-polynomial, see 9. Also, we determine the unique positive root of this polynomial for particular graphs.
Let Γ be a graph with n vertices, where each edge is given an orientation and let Q be the vertex–edge incidence matrix of Γ. Suppose that Γ has a cut-vertex v and Γ−v=ΓV1∪ΓV2. We obtain a relation ...between the Moore–Penrose inverse of the incidence matrix of Γ and of the incidence matrices of the induced subgraphs ΓV1∪{v} and ΓV2∪{v}. The result is used to give a combinatorial interpretation of the Moore–Penrose inverse of the incidence matrix of a graph whose blocks are either cliques or cycles. Moreover we obtain a description of minors of the Moore–Penrose inverse of the incidence matrix when the rows are indexed by cut-edges. The results generalize corresponding results for trees in the literature.
A set R⊆V(G) is a resolving set of a graph G if for all distinct vertices v,u∈V(G) there exists an element r∈R such that d(r,v)≠d(r,u). The metric dimensiondim(G) of the graph G is the cardinality of ...a smallest resolving set of G. A resolving set with cardinality dim(G) is called a metric basis of G. We consider vertices that are in all metric bases, and we call them basis forced vertices. We give several structural properties of sparse and dense graphs where basis forced vertices are present. In particular, we give bounds for the maximum number of edges in a graph containing basis forced vertices. Our bound is optimal whenever the number of basis forced vertices is even. Moreover, we provide a method of constructing fairly sparse graphs with basis forced vertices. We also study vertices which are in no metric basis in connection to cut-vertices and pendants. Furthermore, we show that deciding whether a vertex is in all metric bases is co-NP-hard, and deciding whether a vertex is in no metric basis is NP-hard.
SDN network supports centralized network management by splitting control plane and data plane of forwarding devices and places the network intelligence in a software entity called controller. The ...controller can be placed in selective places of network to effectively monitor and control network activities. Large scale network needs multiple controller to manage control activities of network. In order to identify the optimum number of controllers and its effective locations in the network, a new algorithm is proposed using cut-vertex concept from graph theory. The proposed algorithm is simulated using Mininet SDN emulator. To study the performance of the proposed algorithm, multiple scenarios were used in the simulation and performance was analysed using parameters viz., flow installation time, average latency of network, throughput.
Given a finite group G, the character graph, denoted by Δ(G), for its irreducible character degrees is a graph with vertex set ρ(G) which is the set of prime numbers that divide the irreducible ...character degrees of G, and with {p,q} being an edge if there exists a non-linear χ∈Irr(G) whose degree is divisible by pq. In this paper, on one hand, we proceed by discussing the graphical shape of Δ(G) when it has cut vertices or small number of eigenvalues, and on the other hand we give some results on the group structure of G with such Δ(G). Recently, Lewis and Meng proved the character graph of each solvable group has at most one cut vertex. Now, we determine the structure of character graphs of solvable groups with a cut vertex and diameter 3. Furthermore, we study solvable groups whose character graphs have at most two distinct eigenvalues. Moreover, we investigate the solvable groups whose character graphs are regular with three distinct eigenvalues. In addition, we give some lower bounds for the number of edges of Δ(G).
As a basic problem in graph theory, the maximum flow (max-flow) problem has important applications in networking and communication related areas. The simple path introduced locality is implicit in ...classic max-flow algorithms, i.e., only the vertices in simple paths between source and sink are involved in max-flow calculation. However, this kind of locality is completely ignored in existing acceleration methods, which leads to a lot of useless calculations and seriously degrades the acceleration effect. We propose simple-path locality based max-flow acceleration algorithm (SPLMax) to address the problem, where an overlay graph is built and used to accelerate calculation by only including necessary vertices. Random graph based simulations show that with SPLMax, at best only 0.001% vertices (i.e., 1/71193) in the graph need to be involved in max-flow calculation. For the comparison using real-world graphs, SPLMax has the minimal pre-processing time (at most 109 times faster than other methods) and minimal average max-flow computation time (at most 4.3 times faster than other methods).
Let L be a fixed branch - that is, an irreducible germ of curve - on a normal surface singularity X. If A,B are two other branches, define u_{L}(A,B) := \dfrac {(L \cdot A) \> (L \cdot B)}{A \cdot ...B}, where A \cdot B denotes the intersection number of A and B. Call X arborescent if all the dual graphs of its good resolutions are trees. In a previous paper, the first three authors extended a 1985 theorem of Płoski by proving that whenever X is arborescent, the function u_{L} is an ultrametric on the set of branches on X different from L. In the present paper we prove that, conversely, if u_{L} is an ultrametric, then X is arborescent. We also show that for any normal surface singularity, one may find arbitrarily large sets of branches on X, characterized uniquely in terms of the topology of the resolutions of their sum, in restriction to which u_L is still an ultrametric. Moreover, we describe the associated tree in terms of the dual graphs of such resolutions. Then we extend our setting by allowing L to be an arbitrary semivaluation on X and by defining u_{L} on a suitable space of semivaluations. We prove that any such function is again an ultrametric if and only if X is arborescent, and without any restriction on X we exhibit special subspaces of the space of semivaluations in restriction to which u_{L} is still an ultrametric.
PDF
