اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the $alpha$-index of graphs with pendent paths
79
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For every real $alphainleft[ 0,1right] $, write $A_{alpha}left( Gright) $ for the matrix [ A_{alpha}left( Gright) =alpha Dleft( Gright) +(1-alpha)Aleft( Gright) . ] This paper presents some extremal results about the spectral radius $rho_{alpha}left( Gright) $ of $A_{alpha}left( Gright) $ that generalize previous results about $rho_{0}left( Gright) $ and $rho _{1/2}left( Gright) $. In particular, write $B_{p,q,r}$ be the graph obtained from a complete graph $K_{p}$ by deleting an edge and attaching paths $P_{q}$ and $P_{r}$ to its ends. It is shown that if $alphainleft[ 0,1right) $ and $G$ is a graph of order $n$ and diameter at least $k,$ then% [ rho_{alpha}(G)leqrho_{alpha}(B_{n-k+2,lfloor k/2rfloor,lceil k/2rceil}), ] with equality holding if and only if $G=B_{n-k+2,lfloor k/2rfloor,lceil k/2rceil}$. This result generalizes results of Hansen and Stevanovi{c} cite{HaSt08}, and Liu and Lu cite{LiLu14}.
قيم البحث
اقرأ أيضاً
We describe some metric properties of incomparability graphs. We consider the problem of the existence of infinite paths, either induced or isometric, in the incomparability graph of a poset. Among other things, we show that if the incomparability gr
aph of a poset is connected and has infinite diameter then it contains an infinite induced path and furthermore if the diameter of set of vertices of degree at least $3$ is unbounded the graph contains as an induced subgraph either a comb or a kite. This result allows to draw a line between ages of permutation graphs which are well quasi order and those which are not.
The strong chromatic index of a graph $G$, denoted $chi_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $chi_{s,ell}(G)$, is the lea
st integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatorname{girth}(G) geq 41$ then $chi_{s,ell}(G) leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatorname{girth}(G) geq 30$, then $chi_s(G) leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatorname{girth}(G) geq 28$, then $chi_s(G) leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.
Given a proper edge coloring $varphi$ of a graph $G$, we define the palette $S_{G}(v,varphi)$ of a vertex $v in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $check s(G)$ of $G$ is the minimum number of distin
ct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $check{s}(G)leq 1+max{a,b}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ($textrm{sz}(G)$). This paper is devoted to characterizing the extremal trees and graphs of this new topological invariant. In particular, we proved t
hat the star is a tree having the maximal $textrm{sz}(G)$. Finding a tree with the minimal $textrm{sz}(G)$ is not an easy task to be done. Here, we present the minimal trees up to 25 vertices obtained by computer and describe the regularities which retain in them. Our preliminary computer tests suggest that a tree with the minimal $textrm{sz}(G)$ is also the connected graph of the given order that attains the minimal weighted Szeged index. Additionally, it is proven that among the bipartite connected graphs the complete balanced bipartite graph $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ attains the maximal $textrm{sz}(G)$,. We believe that the $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ is a connected graph of given order that attains the maximum $textrm{sz}(G)$.
Let $G$ be a nonempty simple graph with a vertex set $V(G)$ and an edge set $E(G)$. For every injective vertex labeling $f:V(G)tomathbb{Z}$, there are two induced edge labelings, namely $f^+:E(G)tomathbb{Z}$ defined by $f^+(uv)=f(u)+f(v)$, and $f^-:E
(G)tomathbb{Z}$ defined by $f^-(uv)=|f(u)-f(v)|$. The sum index and the difference index are the minimum cardinalities of the ranges of $f^+$ and $f^-$, respectively. We provide upper and lower bounds on the sum index and difference index, and determine the sum index and difference index of various families of graphs. We also provide an interesting conjecture relating the sum index and the difference index of graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
