On balance and consistency preserving 2-path signed graphs
Abstract
Let Σ = (G, σ) be a balanced and canonically consistent signed graph. The 2-path signed graph Σ#Σ = (G2, σ′) of Σ has the underlying graph as G2 and the sign σ′(uv) of an edge uv in it is −1 whenever in each uv-path of length 2 in Σ all edges are negative; otherwise σ′(uv) is 1. Here, G2 is the graph obtained from G by adding an edge between u and v if there is a path of length 2 between them. In this article, we have investigated balancedness and canonically consistency of 2-path signed graphs Σ#Σ of a balanced and canonically consistent signed graph Σ. The problem has been resolved completely for cycles, star graphs and trees.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.4
References
Jemal Abawajy, Andrei Kelarev and Morshed Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl. 1 (2) (2013), 125–147. http://dx.doi.org/10.5614/ejgta.2013.1.2.6.
B. Devdas Acharya and M. N. Vartak, Open neighborhood graphs, Indian Institute of Technology Department of Mathematics Research Report 6 (1973).
B. Devdas Acharya, A characterization of consistent marked graph, National Academy Science Letters 6 (1983), 431–440.
B. Devdas Acharya, Some further properties of consistent marked graphs, Indian Journal of Pure and Applied Mathematics 15 (8) (1984), 837 – 842.
Lowell W. Beineke and Frank Harary, Consistency in marked digraphs, Journal of Mathematical Psychology 18 (1978), 260–269. https://doi.org/10.1016/0022-2496(78)90054-8.
Lowell W. Beineke and Frank Harary, Consistent graphs with signed points, Rivista di matematica per le scienze economiche e sociali 1 (2) (1978), 81–88. https://link.springer.com/article/10.1007/BF02631374
Dorwin Cartwright and Frank Harary, Structural balance: a generalization of Heider’s theory, Psychological review 63 (5) (1956), 277-293. https://psycnet.apa.org/doi/10.1037/h0046049
Thomas Dittrich, and Gerald Matz, Signal Processing on Signed Graphs: Fundamentals and Potentials. IEEE Signal Processing Magazine 37 (6) (2020) 86–98. https://doi.org/10.1109/MSP.2020.3014060.
J. Escalante, L. Montejano and T. Ceballos, Characterization of n-path graphs and of graphs having n-th root, J. Combin. Theory Ser. B 16 (6) (1974), 282–289.
https://doi.org/10.1016/0095-8956(74)90074-4
M. K. Gill, Contributions to some topics in graph theory and its applications, Ph. D. thesis, The Indian Institute of Technology, Bombay, (1983).
Frank Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (2) (1953), 143–146. doi: 10.1307/mmj/1028989917
Frank Harary, Graph Theory, Addison-Wesley, Reading, MA, (1969).
Frank Harary and Jerald A. Kabell, A simple algorithm to detect balance in signed graphs, Mathematical Social Sciences 1 (1) (1980), 131–136. https://doi.org/10.1016/0165-4896(80)90010-4
Frank Harary and Jerald A. Kabell, Counting balanced signed graphs using marked graphs, Proceedings of the Edinburgh Mathematical Society 24 (2) (1981), 99–104.
https://doi.org/10.1017/S0013091500006398
Frank Harary, Edgar M. Palmer, Robert W. Robinson and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (4) (1977), 295–308.
https://doi.org/10.1002/jgt.3190010405
F. Heider, Attitudes and cognitive organization, The Journal of Psychology 21 (1) (1946), 107–112. https://doi.org/10.1080/00223980.1946.9917275.
Cornelis Hoede, A characterization of consistent marked graphs, J. Graph Theory 16 (1) (1992), 17–23. https://doi.org/10.1002/jgt.3190160104
A. Mukhopadhyay, The square root of a graph, J. Combin. Theory Ser. A 2 (1967), 290–295. https://doi.org/10.1016/S0021-9800(67)80030-9.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, and José M. F. Moura, and Pierre Vandergheynst, Graph Signal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE 106 (5) (2018), 808–828. https://doi.org/10.1109/JPROC.2018.2820126.
S. B. Rao, Characterization of harmonious marked graphs and consistent nets, Journal of Combinatorics, Information and System Sciences, 9 (1984), 97 – 112.
Fred S. Roberts, On the problem of consistent marking of a graph, Linear Algebra and its Applications 217 (1995), 255 – 263. https://doi.org/10.1016/0024-3795(94)00193-H
Fred S Roberts and Shaoji Xu, Characterizations of consistent marked graphs, Discrete Appl. Math. 127 (2) (2003), 357–371. https://doi.org/10.1016/S0166-218X(02)00254-8
Deepak Sehrawat and Bikash Bhattacharjya, Non-isomorphic signatures on some generalised Petersen graph, Electron. J. Graph Theory Appl. 9 (2) (2018), 235–256. http://dx.doi.org/10.5614/ejgta.2021.9.2.1
David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine 30 (3) (2013), 83–98. https://doi.org/10.1109/MSP.2012.2235192.
Deepa Sinha and Ayushi Dhama, Negation switching invariant signed graphs, Electron. J. Graph Theory Appl. 2 (1) (2014), 32–41. http://dx.doi.org/10.5614/ejgta.2013.2.1.3
Deepa Sinha and Pravin Garg, Balance and consistency of total signed graphs. Indian J. Math. 53 (1) (2011), 71– 81. https://doi.org/10.1007/s40009-015-0374-4
Deepa Sinha and Pravin Garg, Characterization of total signed graph and semi-total signed graphs, International Journal of Contemporary Mathematical Sciences 6 (5) (2011), 221– 228.
Deepa Sinha and Pravin Garg, On the regularity of some signed graph structures, AKCE Int. J. Graphs Comb. 8 (1) (2011), 63–74.
https://www.tandfonline.com/doi/abs/10.1080/09728600.2011.12088931
Deepa Sinha and Pravin Garg, A characterization of canonically consistent total signed graphs, Notes on Number Theory and Discrete Mathematics, 19 (3) (2013), 70–77.
Deepa Sinha and Pravin Garg, Canonical consistency of semi-total point signed graphs, Nat. Acad. Sci. Lett. 38 (6) (2015), 497–500.
Deepa Sinha, and Deepakshi Sharma, On 2-path signed graphs, International Workshop on Computational Intelligence (IWCI), IEEE, (2016), 218–220.
https://ieeexplore.ieee.org/document/7860369.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.