For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G)...For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G),α∈[0,1].The Aa-spectral radius is the largest eigenvalue of A_(α)(G).Let G_(n,β) be the set graphs with order n and dissociation numberβ.In this paper,we identify the b with maximal A_(α)-spectral radius among all graphs in G_(n,β).展开更多
Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a nece...Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.展开更多
The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method,...The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O（m） time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.展开更多
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes f...The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.展开更多
A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of ...A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of the interconnection way of blocks and give an explicit expression for the Smith normal form in the case that all cliques have the same size, which generalize the results on determinants.展开更多
基金Supported by NSFC (Nos.12171089,12271235)NSF of Jiangsu (No.BK20190919)NSF of Fujian (No.2021J02048)。
文摘For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G),α∈[0,1].The Aa-spectral radius is the largest eigenvalue of A_(α)(G).Let G_(n,β) be the set graphs with order n and dissociation numberβ.In this paper,we identify the b with maximal A_(α)-spectral radius among all graphs in G_(n,β).
文摘Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.
基金Supported by the National Natural Science Foundation of China(Grant No.11271365)the Domestic Senior Visiting Scholar Program in Higher Occupation Colleges in Jiangsu Province(Grant No.2014FX075)
文摘The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O（m） time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.
基金Supported by the National Natural Science Foundation of China(No.11301475,11126202,11171207)the Nature Science Foundation of Zhejiang Province(No.LQ12A01011)partially supported by The Hong Kong CERG Research Fund PolyU 5515/10H
文摘The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.
基金supported by the National Natural Science Foundation of China(Nos.11501188,11326057,11171102)by Aid program for Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province
文摘A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of the interconnection way of blocks and give an explicit expression for the Smith normal form in the case that all cliques have the same size, which generalize the results on determinants.
