Narrow Results

Let $G$ be a connected graph and $A(G)$ be the adjacency matrix of $G$. Suppose that ${\lambda }_1(G)\ge {\lambda }_2(G)\ge \cdots \ge {\lambda }_n(G)$ are the eigenvalues of $G$. In this paper, we first give a graft transformation on the spectral radius of graphs and then as their application, we determine the extremal graphs with maximum and minimum spectral radii among all clique trees. Furthermore, we also determine the unique graph with maximum spectral radius among all block graphs by using different methods.

A set of vertices D is a dominating set of a graph G=(V, E) if every vertex in V−D is adjacent to at least one vertex in D. The domatic partition of G is the partition of the vertex set V into a maximum number of dominating sets. In this paper, we present efficient parallel algorithms for finding the domatic partition of Interval graphs, Block graphs and K-trees.

We give a lower bound for the Castelnuovo-Mumford regularity of binomial edge ideals of block graphs by computing the two distinguished extremal Betti numbers of a new family of block graphs, called flower graphs. Moreover, we present linear time algorithms to compute the Castelnuovo–Mumford regularity and the Krull dimension of binomial edge ideals of block graphs.

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 sum of all Steiner distances on sets of size $k$ is called the Steiner $k$-Wiener index. A graph $G$ is modular if for every three vertices $x,y,z$ there exists a vertex $w$ that lies on the shortest path between every two vertices of $x,y,z$. The Steiner 3-Wiener index of a modular graph is obtained in terms of its Wiener index. As concrete examples, we discuss the case of Fibonacci, Lucas cubes and the Cartesian product of modular graphs. The Steiner Wiener index of block graphs is also studied.

In a graph $G=(V,E)$, a vertex $v$ dominates a vertex $w$ if either $v=w$ or $v$ is adjacent to $w$. A subset of vertex set $V$ that dominates all the vertices of $G$ is called a dominating set of graph $G$. The minimum cardinality of a dominating set of $G$ is called the domination number of $G$ and is denoted by $\gamma (G)$. A proper coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that any two adjacent vertices get different colors. The minimum number of colors required for a proper coloring of $G$ is called the chromatic number of $G$ and is denoted by $\chi (G)$. A dominator coloring of a graph $G$ is a proper coloring of the vertices of $G$ such that every vertex dominates all the vertices of at least one color class. The minimum number of colors required for a dominator coloring of $G$ is called the dominator chromatic number of $G$ and is denoted by ${\chi }_d(G)$. In this paper, we study the dominator chromatic number for the proper interval graphs and block graphs. We show that every proper interval graph $G$ satisfies $\chi (G)+\gamma (G)-2\le {\chi }_d(G)\le \chi (G)+\gamma (G)$, and these bounds are sharp. For a block graph $G$, where one of the end block is of maximum size, we show that $\chi (G)+\gamma (G)-1\le {\chi }_d(G)\le \chi (G)+\gamma (G)$. We also characterize the block graphs with an end block of maximum size and attaining the lower bound.

In a graph $G=(V,E)$, the degree of a vertex $v\in V$, denoted by $d_G(v)$, is defined as the number of edges incident on $v$. A set $D$ of vertices of $G$ is called a strong dominating set if for every $v\in V\backslash D$, there exists a vertex $u\in D$ such that $uv\in E$ and $d_G(u)\ge d_G(v)$. For a given graph $G$, Min-Strong-DS is the problem of finding a strong dominating set of minimum cardinality. The decision version of Min-Strong-DS is shown to be NP-complete for chordal graphs. In this paper, we present polynomial time algorithms for computing a strong dominating set in block graphs and proper interval graphs, two subclasses of chordal graphs. On the other hand, we show that for a graph $G$ with $n$-vertices, Min-Strong-DS cannot be approximated within a factor of $(\frac{1}{2}-𝜀)lnn$ for every $𝜀>0$, unless NP$\subseteq$DTIME($n^{O(loglogn)}$). We also show that Min-Strong-DS is APX-complete for graphs with maximum degree $3$. On the positive side, we show that Min-Strong-DS can be approximated within a factor of $O(ln\mathrm{\Delta })$ for graphs with maximum degree $\mathrm{\Delta }$.