اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSteiner distance matrix of caterpillar graphs
202
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For a connected graph $G:=(V,E)$, the Steiner distance $d_G(X)$ among a set of vertices $X$ is the minimum size among all the connected subgraphs of $G$ whose vertex set contains $X$. The $k-$Steiner distance matrix $D_k(G)$ of $G$ is a matrix whose rows and columns are indexed by $k-$subsets of $V$. For $k$-subsets $X_1$ and $X_2$, the $(X_1,X_2)-$entry of $D_k(G)$ is $d_G(X_1 cup X_2)$. In this paper, we show that the rank of $2-$Steiner distance matrix of a caterpillar graph on $N$ vertices and with $p$ pendant veritices is $2N-p-1$.
قيم البحث
اقرأ أيضاً
Let $G$ be a simple, connected graph, $mathcal{D}(G)$ be the distance matrix of $G$, and $Tr(G)$ be the diagonal matrix of vertex transmissions of $G$. The distance Laplacian matrix and distance signless Laplacian matrix of $G$ are defined by $mathca
l{L}(G) = Tr(G)-mathcal{D}(G)$ and $mathcal{Q}(G) = Tr(G)+mathcal{D}(G)$, respectively. The eigenvalues of $mathcal{D}(G)$, $mathcal{L}(G)$ and $mathcal{Q}(G)$ is called the $mathcal{D}-$spectrum, $mathcal{L}-$spectrum and $mathcal{Q}-$spectrum, respectively. The generalized distance matrix of $G$ is defined as $mathcal{D}_{alpha}(G)=alpha Tr(G)+(1-alpha)mathcal{D}(G),~0leqalphaleq1$, and the generalized distance spectral radius of $G$ is the largest eigenvalue of $mathcal{D}_{alpha}(G)$. In this paper, we give a complete description of the $mathcal{D}-$spectrum, $mathcal{L}-$spectrum and $mathcal{Q}-$spectrum of some graphs obtained by operations. In addition, we present some new upper and lower bounds on the generalized distance spectral radius of $G$ and of its line graph $L(G)$, based on other graph-theoretic parameters, and characterize the extremal graphs. Finally, we study the generalized distance spectrum of some composite graphs.
A caterpillar graph $T(p_1, ldots, p_r)$ of order $n= r+sum_{i=1}^r p_i$, $rgeq 2$, is a tree such that removing all its pendent vertices gives rise to a path of order $r$. In this paper we establish a necessary and sufficient condition for a real nu
mber to be an eigenvalue of the Randic matrix of $T(p_1, ldots, p_r)$. This result is applied to determine the extremal caterpillars for the Randic energy of $T(p_1,ldots, p_r)$ for cases $r=2$ (the double star) and $r=3$. We characterize the extremal caterpillars for $r=2$. Moreover, we study the family of caterpillars $Tbig(p,n-p-q-3,qbig)$ of order $n$, where $q$ is a function of $p$, and we characterize the extremal caterpillars for three cases: $q=p$, $q=n-p-b-3$ and $q=b$, for $bin {1,ldots,n-6}$ fixed. Some illustrative examples are included.
The Heawood graph is the point-block incidence graph of the Fano plane (the unique Steiner triple system of order 7). We show that the minimum semidefinite rank of this graph is 10. That is, 10 is the smallest number of complex dimensions in which th
is graph has a faithful orthogonal representation, i.e., an assignment of a vector to each vertex such that the edges occur between precisely those vertices given non-orthogonal pairs. Some of our techniques extend to the incidence graphs of Steiner triple systems of larger order, and we include some observations and questions about the more general case.
Building upon the notion of Gutman index $operatorname{SGut}(G)$, Mao and Das recently introduced the Steiner Gutman index by incorporating Steiner distance for a connected graph $G$. The emph{Steiner Gutman $k$-index} $operatorname{SGut}_k(G)$ of $G
$ is defined by $operatorname{SGut}_k(G)$ $=sum_{Ssubseteq V(G), |S|=k}left(prod_{vin S}deg_G(v)right) d_G(S)$, in which $d_G(S)$ is the Steiner distance of $S$ and $deg_G(v)$ is the degree of $v$ in $G$. In this paper, we derive new sharp upper and lower bounds on $operatorname{SGut}_k$, and then investigate the Nordhaus-Gaddum-type results for the parameter $operatorname{SGut}_k$. We obtain sharp upper and lower bounds of $operatorname{SGut}_k(G)+operatorname{SGut}_k(overline{G})$ and $operatorname{SGut}_k(G)cdot operatorname{SGut}_k(overline{G})$ for a connected graph $G$ of order $n$, $m$ edges and maximum degree $Delta$, minimum degree $delta$.
The study of entrywise powers of matrices was originated by Loewner in the pursuit of the Bieberbach conjecture. Since the work of FitzGerald and Horn (1977), it is known that $A^{circ alpha} := (a_{ij}^alpha)$ is positive semidefinite for every entr
ywise nonnegative $n times n$ positive semidefinite matrix $A = (a_{ij})$ if and only if $alpha$ is a positive integer or $alpha geq n-2$. This surprising result naturally extends the Schur product theorem, and demonstrates the existence of a sharp phase transition in preserving positivity. In this paper, we study when entrywise powers preserve positivity for matrices with structure of zeros encoded by graphs. To each graph is associated an invariant called its critical exponent, beyond which every power preserves positivity. In our main result, we determine the critical exponents of all chordal/decomposable graphs, and relate them to the geometry of the underlying graphs. We then examine the critical exponent of important families of non-chordal graphs such as cycles and bipartite graphs. Surprisingly, large families of dense graphs have small critical exponents that do not depend on the number of vertices of the graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
