اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNew upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic
64
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The bondage number $b(G)$ of a graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination number. Let $G$ be embeddable on a surface whose Euler characteristic $chi$ is as large as possible, and assume $chileq0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $Delta(G)$ and the Euler characteristic $chi(G)=chi$. In this paper we prove a better upper bound $b(G)leqDelta(G)+lfloor trfloor$ where $t$ is the largest real root of the cubic equation $z^3 + z^2 + (3chi - 8)z + 9chi - 12=0$; this upper bound is asymptotically equivalent to $b(G)leqDelta(G)+1+lfloor sqrt{4-3chi} rfloor$. We also establish further improved upper bounds for $b(G)$ when the girth, order, or size of the graph $G$ is large compared with its Euler characteristic $chi$.
قيم البحث
اقرأ أيضاً
A complex unit gain graph (or $mathbb{T}$-gain graph) is a triple $Phi=(G, mathbb{T}, varphi)$ ($(G, varphi)$ for short) consisting of a graph $G$ as the underlying graph of $(G, varphi)$, $mathbb{T}= { z in C:|z|=1 } $ is a subgroup of the multiplic
ative group of all nonzero complex numbers $mathbb{C}^{times}$ and a gain function $varphi: overrightarrow{E} rightarrow mathbb{T}$ such that $varphi(e_{ij})=varphi(e_{ji})^{-1}=overline{varphi(e_{ji})}$. In this paper, we investigate the relation among the rank, the independence number and the cyclomatic number of a complex unit gain graph $(G, varphi)$ with order $n$, and prove that $2n-2c(G) leq r(G, varphi)+2alpha(G) leq 2n$. Where $r(G, varphi)$, $alpha(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $A(G, varphi)$, the independence number and the cyclomatic number of $G$, respectively. Furthermore, the properties of the complex unit gain graph that reaching the lower bound are characterized.
We establish a lower bound for the energy of a complex unit gain graph in terms of the matching number of its underlying graph, and characterize all the complex unit gain graphs whose energy reaches this bound.
We give upper bounds on the order of the automorphism group of a simple graph
A fan $F_n$ is a graph consisting of $n$ triangles, all having precisely one common vertex. Currently, the best known bounds for the Ramsey number $R(F_n)$ are $9n/2-5 leq R(F_n) leq 11n/2+6$, obtained by Chen, Yu and Zhao. We improve the upper bound to $31n/6+O(1)$.
For a fixed planar graph $H$, let $operatorname{mathbf{N}}_{mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $operatorname{mathbf{N}}_{mathcal{P}}(n,C
_m)$ is currently known for $min{3,4,5,6,8}$. In this note, we extend this list by establishing $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{10})sim(n/5)^5$ and $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{12})sim(n/6)^6$. We prove this by answering the following question for $min{5,6}$, which is interesting in its own right: which probability mass $mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $mu$ form an $m$-cycle?
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
