...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Ars Combinatoria: An Australian-Canadian Journal of Combinatorics >Pancyclicity, Panconnectivity, and Panpositionability for General Graphs and Bipartite Graphs
【24h】

Pancyclicity, Panconnectivity, and Panpositionability for General Graphs and Bipartite Graphs

机译：普通图和二部图的泛环性，泛连通性和泛置性

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

摘要

A graph G is pancyclic if it contains a cycle of ev-ery length from 3 to I V (G)I inclusive. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d_G(x, y) ≤ l ≤ |V (G)| - 1, where d_G(x, y) denotes the distance between x and y in G. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and any integer k with d_G(x, y) ≤ k ≤ |V (G)|/2, there exists a hamiltonian cycle C of G with d_C(x, y) = k, where d_C(x,y) denotes the distance between x and y in a hamiltonian cycle C of G. It is obvious that panconnected graphs are pancyclic, and panpositionable graphs are pancyclic. The above properties can be studied in bipartite graphs after some modification. A graph H = (V_0 ∪ V_1, E) is bipartite if V(H) = V_0 ∪ V_1 and E(H) is a subset of {(u, v) | u ∈ V_0, v ∈ V_1} . A graph is bipancyclic if it contains a cycle of every even length from 4 to 2 .[|V(H)/2] inclusive. A graph H is bipanconnected if there exists a path of length l joining any two different vertices x and y with d_H(x,y) ≤ 1 ≤ |V(H)|- 1, where d_H(x,y) denotes the distance between x and y in H and 1 - d_H(x,y) is even. A hamiltonian graph H is bipanpositionable if for any two different vertices x and y of H and for any integer k with d_H(x, y) ≤ k < |V(H)|/2, there exists a hamiltonian cycle C of H with d_C(x, y) = k, where d_C(x, y) denotes the distance between x and y in a hamiltonian cycle C of H and k - d_H(x, y) is even. It can be shown that bipanconnected graphs are bipancyclic, and bipanpositionable graphs are bipancyclic. In this paper, we present some examples of pancyclic graphs that are neither panconnected nor panpositionable, some examples of panconnected graphs that are not panpositionable, and some examples of graphs that are panconnected and panpositionable, for nonbipartite graphs. Corresponding examples for bipartite graphs are discussed. The existence of panpositionable (or bipanpositionable, resp.) graphs that are not panconnected (or bipanconnected, resp.) is still an open problem.
机译：如果图G包含一个从3到I V（G）I（含）的平均长度的循环，则它是全循环的。如果存在一个长度为l的路径，连接任意两个不同的顶点x和y，且d_G（x，y）≤l≤| V（G）|，则图G是泛连接的。 -1，其中d_G（x，y）表示G中x和y之间的距离。如果对于G的任意两个不同顶点x和y以及d_G（x，y）≤k的任何整数k，则哈密顿图G是可置位的≤| V（G）| / 2，则存在一个G的哈密顿循环C，其中d_C（x，y）= k，其中d_C（x，y）表示G的哈密顿循环C中的x和y之间的距离。显然，泛连通图是泛圈的，可泛置图是泛圈的。经过一些修改，可以在二部图中研究以上特性。如果V（H）= V_0∪V_1并且E（H）是{（u，v）| |的子集，则图H =（V_0∪V_1，E）是二分的。 u∈V_0，v∈V_1}。如果图包含一个从4到2。[| V（H）/ 2]（含两端）的偶数长度的循环，则该图为双全圈图。如果存在一个长度为l的路径，将任意两个不同的顶点x和y连接起来，且d_H（x，y）≤1≤| V（H）| -1，则图H是双连通的，其中d_H（x，y）表示距离在H和1中的x和y之间-d_H（x，y）是偶数。如果对于H的任意两个不同顶点x和y以及对于d_H（x，y）≤k <| V（H）| / 2的任何整数k，存在一个H的哈密顿循环C，则哈密顿图H是可重叠的d_C（x，y）= k，其中d_C（x，y）表示H的哈密顿循环C中的x和y之间的距离，并且k-d_H（x，y）是偶数。可以证明，双全连通图是双全环的，而双全置图是双全环的。在本文中，对于非二分图，我们给出了一些既不具有泛连接性也不具有泛位置性的泛环图示例，一些具有泛位置不相关性的泛连接图示例以及一些具有泛连接性和泛位置性的图示例。讨论了二部图的相应示例。没有全连接（或双连接，分别）的全连接图（或双连接，分别）的存在仍然是一个未解决的问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号