Gossiping Properties of the Modified Knödel Graphs
Keywords:
Graphs, Networks, Telephone problem, Gossip problem, Knödel graphsAbstract
In this paper we consider the gossiping process implemented on several modi¯cations of KnÄodel graphs. We show the ability of Knödel graphs to remain good network topology for gossiping even in case of cyclic permutation of its edge weights. The results shown in this paper could help us to construct edge-disjoint paths between any pairs of vertices of the Knödel graph.
References
B.Baker and R.Shostak, “Gossips and telephones", Discrete Mathematics, vol. 2, pp. 191-193, 1972.
R.T. Bumby, “A problem with telephones", SIAM Journal on Algebraic Discrete Methods, vol. 2, pp. 13-18, 1981.
A. Hajnal, E.C. Milner and E. Szemeredi, “A cure for the telephone disease", Canadian Mathematical Bulletin., vol. 15, pp. 447-450, 1972.
T. Tijdeman, “On a telephone problem", Nieuw Archief voor Wiskunde vol. 3, pp. 188-192, 1971.
A. Seress, “Quick gossiping by conference calls", SIAM Journal on Discrete Mathematics, vol. 1, pp. 109-120, 1988.
D .B. West, “Gossiping without duplicate transmissions", SIAM Journal on Algebraic Discrete Methods, vol. 3, pp. 418-419, 1982.
G. Fertin and A . Respaud, "A survey on Knödel graphs", Discrete Applied Mathematics, vol. 137, no. 2, pp. 173-195, 2003.
R. Labahn, “Kernels of minimum size gossip schemes", Discrete Mathematics, vol. 143, pp. 99-139, 1995.
R. Labahn, “Some minimum gossip graphs", Networks, vol. 23, pp. 333-341, 1993.
G. Fertin and R. Labahn, “Compounding of gossip graphs", Networks, vol. 36, pp. 126-137, 2000.
A. Bavelas, “Communication pattern in task-oriented groups", Journal of the Acoustical Society of America vol. 22, pp. 725-730, 1950.
W. Knodel, “New gossips and telephones", Discrete Mathematics, vol. 13, pp. 95, 1975.
Z. Ho and M. Shigeno, “New bounds on the minimum number of calls in failure-tolerant Gossiping", Networks, vol. 53, pp. 35-38, 2009.
K. A. Berman and M. Hawrylycz, “Telephone problems with failures", SIAM Journal on Algebraic Discrete Methods, vol. 7, pp. 13-17, 1987.
R.W. Haddad, S. Roy and A .A. Schaffer, “On gossiping with faulty telephone lines", SIAM Journal on Algebraic Discrete Methods, vol. 8, pp. 439-445, 1987.
T. Hasunama and H. Nagamochi, “Improved bounds for minimum fault-tolerant gossip graphs", Lecture Notes in Computer Science, vol. 6986, pp. 203-214, 2011.
V. H. Hovnanyan, H. E. Nahapetyan, Su. S. Poghosyan and V.S. Poghosyan, “Tighter upper bounds for the minimum number of calls and rigorous minimal time in faulttolerant gossip schemes", arXiv:1304.5633.
Sandra M. Hedetniemi, Stephen T. Hedetniemi, Arthur L. Liestman, “A survey of gossiping and broadcasting in communication networks", Networks, vol. 18, pp. 319- 349, 1988.
D. B. West, “A class of solutions to the gossip problem", part I, Discrete Mathematics, vol. 39, no. 3, pp. 307-326, 1982:
A. Seress, “Quick Gossiping without duplicate transmissions", Graphs and Combinatorics, vol. 2, pp. 363-381, 1986.
P. Fraigniaud, A. L. Liestman and D. Soiteau, “Open problems", Parallel Processing Letters, vol. 3, no. 4, pp. 507-524, 1993.
V. H. Hovnanyan, Su. S. Poghosyan and V. S. Poghosyan, “Method of local interchange to investigate Gossip problems", Transactions of IIAP of NAS RA, Mathematical P roblems of Computer Science, vol. 40, pp. 5-12, 2013.
L.H. Khachatrian, H .S. Harutounian, “On Optimal Broadcast Graphs", Proc. of the fourth Int. Colloquium on Coding Theory, 65-72, Armenia, 1991.
D. B. West, “A class of solutions to the gossip problem", part II, Disc. Math., vol. 40, no. 1, pp. 87-113, 1982:
D. B. West, “A class of solutions to the gossip problem", part III, Discrete Mathematics, vol. 40, no. 2-3, pp. 285-310, 1982.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
