...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the remoteness function in median graphs
【24h】

On the remoteness function in median graphs

机译：关于中位数图的远程功能

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex X E V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and in edges, decides in O(m log n) time whether G is a median graph with geodetic number 2.
机译：图G上的轮廓是任何非空的多集，其元素是G的顶点。相应的远程功能将每个x与X E V（G）的关系指定为x到轮廓中各个顶点的距离之和。从超立方体中的远程函数的一些不错且有用的属性开始，针对超立方体中的等距嵌入，在任意中值图中研究了遥函数。具体地，找到中位图G中的顶点之间的关系，该中值图G的远程函数是最大的（G的后向集合）与宿主超立方体的后向集合。对于奇数轮廓，反时差集合是位于中位数图的严格边界中的独立集，但存在中位数图，其中特殊的偶数轮廓产生恒定的遥函数。我们用两种方式对这种中值图进行刻画：作为周向横向数为2的图，以及作为大地测量数等于2的图。最后，我们给出一种算法，给定在n个顶点和边上的图G，确定在O（m log n）时间中G是否为大地测量数为2的中位数图。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号