No Arabic abstract
The distance energy of a simple connected graph $G$ is defined as the sum of absolute values of its distance eigenvalues. In this paper, we mainly give a positive answer to a conjecture of distance energy of clique trees proposed by Lin, Liu and Lu [H.~Q.~ Lin, R.~F.~Liu, X.~W.~Lu, The inertia and energy of the distance matrix of a connected graph, {it Linear Algebra Appl.,} 467 (2015), 29-39.]
Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the local
The emph{distance matrix} of a simple connected graph $G$ is $D(G)=(d_{ij})$, where $d_{ij}$ is the distance between the vertices $i$ and $j$ in $G$. We consider a weighted tree $T$ on $n$ vertices with edge weights are square matrix of same size. The distance $d_{ij}$ between the vertices $i$ and $j$ is the sum of the weight matrices of the edges in the unique path from $i$ to $j$. In this article we establish a characterization for the trees in terms of rank of (matrix) weighted Laplacian matrix associated with it. Then we establish a necessary and sufficient condition for the distance matrix $D$, with matrix weights, to be invertible and the formula for the inverse of $D$, if it exists. Also we study some of the properties of the distance matrices of matrix weighted trees in connection with the Laplacian matrices, g-inverses and eigenvalues.
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
The Ramsey number r(K_s,Q_n) is the smallest positive integer N such that every red-blue colouring of the edges of the complete graph K_N on N vertices contains either a red n-dimensional hypercube, or a blue clique on s vertices. Answering a question of Burr and ErdH{o}s from 1983, and improving on recent results of Conlon, Fox, Lee and Sudakov, and of the current authors, we show that r(K_s,Q_n) = (s-1) (2^n - 1) + 1 for every s in N and every sufficiently large n in N.
We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2 - r - 1)n - r + 1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of $K_r$, and that this number of vertices cannot be reduced.