A block graph is a graph in which every block is a complete graph. Denote by Kn,q the set of block graphs with n vertices and all blocks on q+1 vertices for every q≥2. Recently, Zhao and Liu (2023) ...determined the minimum spectral radius of graphs in Kn,q, which verified a conjecture posed by Conde et al. (2022). Replacing the complete graph by a general block or a cycle, we define a generalized block graph or a cycle tree, respectively. Let Bn,q (resp. Cn,q) be the set of generalized block graphs (resp. cycle trees) on n vertices and in which each block is of order q+1 for q≥2. In this paper, we obtain the maximum/minimum spectral radius of a graph in Cn,q. Furthermore, we determine the extremal graph attaining the minimum spectral radius among graphs in Bn,q, which coincides with that in Cn,q.
A connected graph is called a block graph if each of its blocks is a complete graph. Let Bl(k,φ) be the class of block graphs on k vertices with given dissociation number φ. In this article, we have ...shown the existence and uniqueness of a block graph Bk,φ in Bl(k,φ) that maximizes the spectral radius ρ(G) among all graphs G in Bl(k,φ). Furthermore, we also provide bounds on ρ(Bk,φ).
•A connected graph is called a block graph if each of its blocks is a complete graph. Let Bl(k,φ) be the class of block graphs on k vertices with given dissociation number φ.•We are interested to find a graph that uniquely attains maximum spectral radius (with respect to the adjacency matrix) in Bl(k,φ).•We achieve our goal by first observing a few properties of graphs with maximum spectral radius in Bl(k,φ). Further, we prove that graphs with these properties are uniquely determined upto graph isomorphism.•We also obtain bounds on the spectral radius for the extremal graph in Bl(k,φ).
A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by ι(G), is the minimum cardinality of an ...isolating set of G. It is known that ι(G)≤n/3, if G is a connected graph of order n, n≥3, distinct from C5. The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number equal to n/3. Moreover, we provide a family of general graphs attaining this upper bound on the isolation number.
•In the revised manuscript, Lemma 2:2 and Proposition 2:3 (Lemma 2:1 and Proposition 2:2 in the previous draft) are modified in view of comments of Referee 2.•In view of comments of Referee 2, to ...show the Lemma 2:6 (Lemma 2:5 in the previous draft) is true for the Case 3 (q>p and n>m) whenever m=1, we subdivide the case as p=q−1 and p<q−1.
A connected graph is called a bi-block graph if each of its blocks is a complete bipartite graph. Let B(k,α) be the class of bi-block graph on k vertices with given independence number α. It is easy to see that every bi-block graph is a bipartite graph. For a bipartite graph G on k vertices, the independence number α(G) satisfies ⌈k2⌉≤α(G)≤k−1. In this article, we prove that the maximum spectral radius ρ(G) among all graphs G in B(k,α), is uniquely attained for the complete bipartite graph Kα,k−α.
An orientation D of a graph G=(V,E) is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each v∈V(G), the indegree of v in D, ...denoted by dD−(v), is the number of arcs with head v in D. An orientation D of G is proper if dD−(u)≠dD−(v), for all uv∈E(G). An orientation with maximum indegree at most k is called a k-orientation. The proper orientation number of G, denoted by χ→(G), is the minimum integer k such that G admits a proper k-orientation. We prove that determining whether χ→(G)≤k is NP-complete for chordal graphs of bounded diameter, but can be solved in linear-time in the subclass of quasi-threshold graphs. When parameterizing by k, we argue that this problem is FPT for chordal graphs and argue that no polynomial kernel exists, unless NP⊆coNP/poly. We present a better kernel to the subclass of split graphs and a linear kernel to the class of cobipartite graphs.
Concerning bounds, we first prove that if G is split, then χ→(G)≤2ω(G)−2 and that if G is a k-uniform block graph, then χ→(G)≤3k−2. These bounds are tight. We also present new families of trees having proper orientation number at most 2 and at most 3. Actually, we prove a general bound stating that any graph G having no adjacent vertices of degree at least c+1 has proper orientation number at most c. This implies new classes of (outer)planar graphs with bounded proper orientation number. We also prove that maximal outerplanar graphs G whose weak-dual is a path satisfy χ→(G)≤13. Finally, we present simple bounds to the classes of chordal claw-free graphs and cographs.
A q-analogue of the distance matrix (called q-distance matrix) of graphs, defined by Yan and Yeh (2007) 19, is revisited, which is formed from the distance matrix by replacing each nonzero entry α by ...1+q+…+qα−1 (which would be reduced to α by setting q=1). This concept was also proposed by Bapat et al. (2006) 3. A graph is called a block graph if every block is a clique (not necessarily of the same order). In this paper, the formula for the inverse of q-distance matrix of block graphs is presented, which generalizes some classical results about the inverse of distance matrix.
We study the problem of finding a set of p connected vertices in a block graph to minimize the convex combination of the median and the center objective functions. This problem is called the ...connected p-centdian problem on block graphs. In the scope of this paper, we always focus on unweighted block graphs. For block graphs with two different edge lengths, the problem is NP-complete. For block graphs with uniform edge lengths, we focus on a special case of the connected p-centdian problem, namely where the median and the center functions receive equal weight. Concerning this specific problem, we consider a lexicographic order based on certain labels of the vertices and prove that there exists a connected p-centdian that contains a predetermined 1-centdian on the underlying graph. Applying this result, we develop a linear time algorithm for the problem. Finally, the problem under the general convex combination of the median and the center functions is also discussed.
Steiner Wiener index of block graphs Kovše, Matjaž; Rasila, V A.; Vijayakumar, Ambat
AKCE international journal of graphs and combinatorics,
09/2020, Letnik:
ahead-of-print, Številka:
ahead-of-print
Journal Article
Recenzirano
Odprti dostop
Let S be a set of vertices of a connected graph G. The Steiner distance of S is the minimum size of a connected subgraph of G containing all the vertices of S. The Steiner k-Wiener index is the sum ...of all Steiner distances on sets of k vertices of G. Different simple methods for calculating the Steiner k-Wiener index of block graphs are presented.
•The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied.•A (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ is ...presented.•The approximation ratio is improved to Δ if the maximum degree Δ is a constant.•The polynomial-time solvability of MaxHS on block/interval graphs is proved.•The NP-hardness of MaxHS on bipartite/cubic graphs is proved.
In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.
PDF
