论文标题
有限度量维度图的极端结果
Extremal results for graphs of bounded metric dimension
论文作者
论文摘要
公制维度是由机器人导航，药物设计和图像处理中的问题激励的图参数。在本文中，我们回答了（Geneson，度量维度和模式避免的图形，避免，离散的Appl。284，2020，1-7）的图表中的几个开放性极端问题。 Specifically, we construct a new family of graphs that allows us to determine the maximum possible degree of a graph of metric dimension at most $k$, the maximum possible degeneracy of a graph of metric dimension at most $k$, the maximum possible chromatic number of a graph of metric dimension at most $k$, and the maximum $n$ for which there exists a graph of metric dimension at most $k$ that contains $K_{n, n}$. 我们还调查了一种称为边缘度量尺寸的公制尺寸的变体，并通过表明$ p_n^{d} $的边缘度量尺寸为$ n \ geq d^{d-1} $，从同一论文中解决了另一个论文的另一个问题。此外，我们使用概率参数从同一论文中的另一个开放问题上取得了进展，表明最大可能的$ k $ g $ k $的最大可能集团数为$ 2^{θ（k）} $。我们还通过找到一个新的三胞胎$（x，y，n）$的家族的$ x $ x $ x $ x $，边缘度量$ y $ y $ y $（x，y，n）$的家族，从（N. Zubrilina，n。Zubrilina，在图形的边缘维度上，离散数学的边缘维度，离散数学。特别是，我们表明，对于每个整数$ k> 0 $，存在图形$ g $带公制尺寸$ k $，边缘度量尺寸$ 3^k（1-o（1））$，并订购$ 3^k（1+o（1））$。
Metric dimension is a graph parameter motivated by problems in robot navigation, drug design, and image processing. In this paper, we answer several open extremal problems on metric dimension and pattern avoidance in graphs from (Geneson, Metric dimension and pattern avoidance, Discrete Appl. Math. 284, 2020, 1-7). Specifically, we construct a new family of graphs that allows us to determine the maximum possible degree of a graph of metric dimension at most $k$, the maximum possible degeneracy of a graph of metric dimension at most $k$, the maximum possible chromatic number of a graph of metric dimension at most $k$, and the maximum $n$ for which there exists a graph of metric dimension at most $k$ that contains $K_{n, n}$. We also investigate a variant of metric dimension called edge metric dimension and solve another problem from the same paper for $n$ sufficiently large by showing that the edge metric dimension of $P_n^{d}$ is $d$ for $n \geq d^{d-1}$. In addition, we use a probabilistic argument to make progress on another open problem from the same paper by showing that the maximum possible clique number of a graph of edge metric dimension at most $k$ is $2^{Θ(k)}$. We also make progress on a problem from (N. Zubrilina, On the edge dimension of a graph, Discrete Math. 341, 2018, 2083-2088) by finding a family of new triples $(x, y, n)$ for which there exists a graph of metric dimension $x$, edge metric dimension $y$, and order $n$. In particular, we show that for each integer $k > 0$, there exist graphs $G$ with metric dimension $k$, edge metric dimension $3^k(1-o(1))$, and order $3^k(1+o(1))$.
