Geodesic
Characterizing which Powers of Hypercubes and Folded Hypercubes Are Divisor Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 301-311.

Voir la notice de l'article provenant de la source Library of Science

In this paper, we show that Q_n^k is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Q_n^k is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQ_n is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQ_n is not a divisor graph. For n ≥ 5, we show that (FQ_n)^k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.
Keywords: hypercube, folded-hypercube, divisor graph, power of a graph 
@article{DMGT_2015_35_2_a8,
     author = {AbuHijleh, Eman A. and AbuGhneim, Omar A. and Al-Ezeh, Hasan},
     title = {Characterizing which {Powers} of {Hypercubes} and {Folded} {Hypercubes} {Are} {Divisor} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {301--311},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a8/}
}
TY  - JOUR
AU  - AbuHijleh, Eman A.
AU  - AbuGhneim, Omar A.
AU  - Al-Ezeh, Hasan
TI  - Characterizing which Powers of Hypercubes and Folded Hypercubes Are Divisor Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 301
EP  - 311
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a8/
LA  - en
ID  - DMGT_2015_35_2_a8
ER  - 
%0 Journal Article
%A AbuHijleh, Eman A.
%A AbuGhneim, Omar A.
%A Al-Ezeh, Hasan
%T Characterizing which Powers of Hypercubes and Folded Hypercubes Are Divisor Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 301-311
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a8/
%G en
%F DMGT_2015_35_2_a8
AbuHijleh, Eman A.; AbuGhneim, Omar A.; Al-Ezeh, Hasan. Characterizing which Powers of Hypercubes and Folded Hypercubes Are Divisor Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 301-311. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a8/

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

[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

[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

[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

[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

[12] A.D. Pollington, There is a long path in the divisor graph, Ars Combin. 16-B (1983) 303-304.

[13] C. Pomerance, On the longest simple path in the divisor graph, Congr. Numer. 40 (1983) 291-304.

[14] G.S. Singh, G. Santhosh, Divisor graph-I, preprint.