Panconnectivity of Cartesian product graphs

Author： Lu You   Xu Jun-Ming  

Publisher： Springer Publishing Company

ISSN： 0920-8542

Source： The Journal of Supercomputing, Vol.56, Iss.2, 2011-05, pp. : 182-189

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length l for each l such that d G (x,y)≤l≤n−1, where d G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q n (k 1,k 2,…,k n ) is panconnected if and only if k i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube $Q^{3}_{n}$ is panconnected.

Related content

Embedding Cartesian Products of Graphs into de Bruijn Graphs

By Andreae T.   Nolle M.   Schreiber G.  

Journal of Parallel and Distributed Computing, Vol. 46, Iss. 2, 1997-11 ,pp. : 194-200 (7)

Academic Press

Access to resources Recommend Favorite

Cartesian logic

By Freyd  

Theoretical Computer Science, Vol. 278, Iss. 1, 2002-05 ,pp. : 3-21 (19)

Elsevier

Access to resources Recommend Favorite

Modelling and controlling product manufacturing systems using bond-graphs and state equations: continuous systems and discrete systems which can be represented by continuous models

By Ferney M.  

Production Planning and Control, Vol. 11, Iss. 1, 2000-01 ,pp. : 7-19 (13)

Taylor & Francis Ltd

Access to resources Recommend Favorite

An axiomatization of graphs

By Bozapalidis Symeon   Kalampakas Antonios  

Acta Informatica, Vol. 41, Iss. 1, 2004-11 ,pp. : 19-61 (43)

Springer Publishing Company

Access to resources Recommend Favorite

From Existential Graphs to Conceptual Graphs

By  

International Journal of Conceptual Structures and Smart Applications (IJCSSA), Vol. 1, Iss. 1, 2013-01 ,pp. : 39-72 (34)

IGI Global_journal

Access to resources Recommend Favorite