# Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs

Eman A. AbuHijleh; Omar A. AbuGhneim; Hasan Al-Ezeh

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 2, page 301-311
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topEman A. AbuHijleh, Omar A. AbuGhneim, and Hasan Al-Ezeh. "Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 301-311. <http://eudml.org/doc/271090>.

@article{EmanA2015,

abstract = {In this paper, we show that Qkn is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Qkn is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQn is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQn is not a divisor graph. For n ≥ 5, we show that (FQn)k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.},

author = {Eman A. AbuHijleh, Omar A. AbuGhneim, Hasan Al-Ezeh},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hypercube; folded-hypercube; divisor graph; power of a graph},

language = {eng},

number = {2},

pages = {301-311},

title = {Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs},

url = {http://eudml.org/doc/271090},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Eman A. AbuHijleh

AU - Omar A. AbuGhneim

AU - Hasan Al-Ezeh

TI - Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 2

SP - 301

EP - 311

AB - In this paper, we show that Qkn is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Qkn is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQn is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQn is not a divisor graph. For n ≥ 5, we show that (FQn)k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.

LA - eng

KW - hypercube; folded-hypercube; divisor graph; power of a graph

UR - http://eudml.org/doc/271090

ER -

## References

top- [1] E.A. AbuHijleh, O.A. AbuGhneim and H. Al-Ezeh, Characterizing when powers of a caterpillar are divisor graphs, Ars Combin. 113 (2014) 85-95.
- [2] S. Aladdasi, O.A. AbuGhneim and H. Al-Ezeh, Divisor orientations of powers of paths and powers of cycles, Ars Combin. 94 (2010) 371-380.
- [3] S. Aladdasi, O.A. AbuGhneim and H. Al-Ezeh, Characterizing powers of cycles that are divisor graphs, Ars Combin. 97 (2010) 447-451.
- [4] S. Al-Addasi, O.A. AbuGhneim and H. Al-Ezeh, Merger and vertex splitting in divisor graphs, Int. Math. Forum 5 (2010) 1861-1869. Zbl1217.05196
- [5] S. Aladdasi, O.A. AbuGhneim and H. Al-Ezeh, Further new properties of divisor graphs, J. Combin. Math. Combin. Comput. 81 (2012) 261-272.
- [6] G. Agnarsson, R. Greenlaw, Graph Theory: Modeling Applications and Algorithms (Pearson, NJ, USA, 2007).
- [7] G. Chartrand, R. Muntean, V. Seanpholphat and P. Zang, Which graphs are divisor graphs, Congr. Numer. 151 (2001) 180-200.
- [8] P. Erdős, R. Frued and N. Hegyvári, Arithmetical properties of permutations of integers, Acta Math. Hungar. 41 (1983) 169-176. doi:10.1007/BF01994075[Crossref] Zbl0518.10063
- [9] S.Y. Hsieh, C.N. Kuo, Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes, Comput. Math. Appl. 53 (2006) 1040-1044. doi:10.1016/j.camwa.2006.10.033[WoS][Crossref]
- [10] M. Kobeissi, M. Mollard, Disjoint cycles and spanning graphs of hypercubes, Discrete Math. 288 (2004) 73-87. doi:10.1016/j.disc.2004.08.005[Crossref] Zbl1057.05049
- [11] O. Melnikov, V. Sarvanov, R. Tyshkevich, V. Yemelichev and I. Zverovich, Exercises in Graph Theory (Netherlands, Kluwer Academic Publishers, 1998). doi:10.1007/978-94-017-1514-0[Crossref] Zbl0913.05037
- [12] A.D. Pollington, There is a long path in the divisor graph, Ars Combin. 16-B (1983) 303-304. Zbl0536.05041
- [13] C. Pomerance, On the longest simple path in the divisor graph, Congr. Numer. 40 (1983) 291-304. Zbl0546.05038
- [14] G.S. Singh, G. Santhosh, Divisor graph-I, preprint.