For a graph $G$, $ mp(G) $ is the multipacking number, and $\gamma_b(G)$ is the broadcast domination number. It is known that $mp(G)\leq \gamma_b(G)$ and $\gamma_b(G)\leq 2mp(G)+3$ for any graph $G$, and it was shown that $\gamma_b(G)-mp(G)$ can be arbitrarily large for connected graphs. It is conjectured that $\gamma_b(G)\leq 2mp(G)$ for any general graph $G$. We show that, for any cactus graph $G$, $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for cactus graphs and asteroidal triple-free graphs by constructing an infinite family of cactus graphs which are also asteroidal triple-free graphs such that the ratio $\gamma_b(G)/mp(G)=4/3$, with $mp(G)$ arbitrarily large. This result shows that, for cactus graphs, the bound $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$ cannot be improved to a bound in the form $\gamma_b(G)\leq c_1\cdot mp(G)+c_2$, for any constant $c_1<4/3$ and $c_2$. Moreover, we provide an $O(n)$-time algorithm to construct a multipacking of cactus graph $G$ of size at least $ \frac{2}{3}mp(G)-\frac{11}{3} $, where $n$ is the number of vertices of the graph $G$. The hyperbolicity of the cactus graph class is unbounded. For $0$-hyperbolic graphs, $mp(G)=\gamma_b(G)$. Moreover, $mp(G)=\gamma_b(G)$ holds for the strongly chordal graphs which is a subclass of $\frac{1}{2}$-hyperbolic graphs. Now it's a natural question: what is the minimum value of $\delta$, for which we can say that the difference $ \gamma_{b}(G) - mp(G) $ can be arbitrarily large for $\delta$-hyperbolic graphs? We show that the minimum value of $\delta$ is $\frac{1}{2}$ using a construction of an infinite family of cactus graphs with hyperbolicity $\frac{1}{2}$.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
140+阅读 · 2020年7月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
144+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
学习自然语言处理路线图
专知会员服务
133+阅读 · 2019年9月24日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
CNN 反向传播算法推导
统计学习与视觉计算组
28+阅读 · 2017年12月29日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Arxiv
16+阅读 · 2022年5月17日
Arxiv
18+阅读 · 2021年3月16日
Recent advances in deep learning theory
Arxiv
50+阅读 · 2020年12月20日
A survey on deep hashing for image retrieval
Arxiv
14+阅读 · 2020年6月10日
VIP会员
相关资讯
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
CNN 反向传播算法推导
统计学习与视觉计算组
28+阅读 · 2017年12月29日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员