On balance and consistency preserving 2-path signed graphs

Kshittiz Chettri, Biswajit Deb, Anjan Gautam


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.


signed graphs, balance, consistent, 2-path signed graphs

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.4


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.


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.


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.


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.


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.



  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats