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

Abstract

top
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.

How to cite

top

Eman 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. [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. [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. [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. [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. [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. [6] G. Agnarsson, R. Greenlaw, Graph Theory: Modeling Applications and Algorithms (Pearson, NJ, USA, 2007). 
  7. [7] G. Chartrand, R. Muntean, V. Seanpholphat and P. Zang, Which graphs are divisor graphs, Congr. Numer. 151 (2001) 180-200. 
  8. [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. [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. [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. [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. [12] A.D. Pollington, There is a long path in the divisor graph, Ars Combin. 16-B (1983) 303-304. Zbl0536.05041
  13. [13] C. Pomerance, On the longest simple path in the divisor graph, Congr. Numer. 40 (1983) 291-304. Zbl0546.05038
  14. [14] G.S. Singh, G. Santhosh, Divisor graph-I, preprint. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.