Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 multiplicative 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?
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
