ON $\bullet$-LICT signed graohs $L_{\bullet_c}(S)$ and $\bullet$-LINE signed graohs $L_\bullet(S)$

Document Type : Research Paper

Authors

DELHI TECHNOLOGICAL UNIVERSITY, DELHI - INDIA

Abstract

A signed graph (or‎, ‎in short‎, sigraph) $S=(S^u,\sigma)$ consists of an underlying graph $S^u‎ :‎=G=(V,E)$ and a function $\sigma:E(S^u)\longrightarrow \{+,-\}$‎, ‎called the signature of $S$‎. ‎A marking of $S$ is a function $\mu:V(S)\longrightarrow \{+,-\}$‎. ‎The canonical marking of a signed graph $S$‎, ‎denoted $\mu_\sigma$‎, ‎is given as $$\mu_\sigma(v)‎ :‎= \prod_{vw\in E(S)}\sigma(vw).$$‎
‎The line graph of a graph $G$‎, ‎denoted $L(G)$‎, ‎is the graph in which edges of $G$ are represented as vertices‎, ‎two of these vertices are adjacent if the corresponding edges are adjacent in $G$‎. ‎There are three notions of a line signed graph of a signed graph $S=(S^u,\sigma)$ in the literature‎, ‎viz.‎, ‎$L(S)$‎, ‎$L_\times(S)$ and $L_\bullet(S)$‎, ‎all of which have $L(S^u)$ as their underlying graph; only the rule to assign signs to the edges of $L(S^u)$ differ‎. ‎Every edge $ee'$ in $L(S)$ is negative whenever both the adjacent edges $e$ and $e'$ in S are negative‎, ‎an edge $ee'$ in $L_\times(S)$ has the product $\sigma(e)\sigma(e')$ as its sign and an edge $ee'$ in $L_\bullet(S)$ has $\mu_\sigma(v)$ as its sign‎, ‎where $v\in V(S)$ is a common vertex of edges $e$ and $e'$‎.

‎The line-cut graph (or‎, ‎in short‎, lict graph) of a graph $G=(V,E)$‎, ‎denoted by $L_c(G)$‎, ‎is the graph with vertex set $E(G)\cup C(G)$‎, ‎where $C(G)$ is the set of cut-vertices of $G$‎, ‎in which two vertices are adjacent if and only if they correspond to adjacent edges of $G$ or one vertex corresponds to an edge $e$ of $G$ and the other vertex corresponds to a cut-vertex $c$ of $G$ such that $e$ is incident with $c$‎.

‎In this paper‎, ‎we introduce dot-lict signed graph (or $\bullet$-lict signed graph} $L_{\bullet_c}(S)$‎, ‎which has $L_c(S^u)$ as its underlying graph‎. ‎Every edge $uv$ in $L_{\bullet_c}(S)$ has the sign $\mu_\sigma(p)$‎, ‎if $u‎, ‎v \in E(S)$ and $p\in V(S)$ is a common vertex of these edges‎, ‎and it has the sign $\mu_\sigma(v)$‎, ‎if $u\in E(S)$ and $v\in C(S)$‎. ‎we characterize signed graphs on $K_p$‎, ‎$p\geq2$‎, ‎on cycle $C_n$ and on $K_{m,n}$ which are $\bullet$-lict signed graphs or $\bullet$-line signed graphs‎, ‎characterize signed graphs $S$ so that $L_{\bullet_c}(S)$ and $L_\bullet(S)$ are balanced‎. ‎We also establish the characterization of signed graphs $S$ for which $S\sim L_{\bullet_c}(S)$‎, ‎$S\sim L_\bullet(S)$‎, ‎$\eta(S)\sim L_{\bullet_c}(S)$ and $\eta(S)\sim L_\bullet(S)$‎, ‎here $\eta(S)$ is negation of $S$ and $\sim$ stands for switching equivalence‎.

Keywords

Main Subjects


[1] R. P. Abelson and M. J. Rosenberg, Symoblic psychologic: A model of attitudinal cognition, Behav. Sci., 3 (1958) 1-13.

[2] M. Acharya, R. Jain and S. Kansal, Characterization of line-cut graphs, Graph Theory Notes of New York, 66 (2014) 43-46.

[3] B. D. Acharya, Signed Intersection Graphs, J. Discrete Math. Sci. and Cryptogr., 13 (2010) 553-569.

[4] M. Acharya, x-Line signed graphs, J. Combin. Math. and Combin. Comp., 69 (2009) 103-111.

[5] M. Behzad and G. T. Chartrand, Line coloring of signed graphs, Elem. Math., 24 (1969) 49-52.

[6] F. Harary, Graph Theory, Addison-Wesley Publ. Comp., Massachusetts, Reading, 1969.

[7] F. Harary, On the notion of balance of a signed graph, Michigan Math. J., 2 (1953-54) 143-146.

[8] F. Harary, Structural duality, Behavioral Sci., 2 (1957) 255-265.

[9] V. R. Kulli and M. H. Muddebihal, The lict graph and litact graph of a graph, J. of Analysis and Comput., 2 (2006) 33-43.

[10] E. Sampathkumar, Point-signed and line-signed graphs, Nat. Acad. Sci. Lett., 7 (1984) 91-93.

[11] D. Sinha, New frontiers in the theory of signed graphs, Ph.D. Thesis, University of Delhi, India, 2005.

[12] T. Sozánsky, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory, 4 (1980) 127-144.

[13] T. Zaslavsky, Signed graphs, Discrete Appl. Math., 4 (1982) 47-74.

[14] T. Zaslavsky, Signed analogs of bipartite graphs, Discrete Appl. Math., 179 (1998) 205-216.
  • Receive Date: 29 September 2013
  • Revise Date: 01 December 2014
  • Accept Date: 02 February 2015
  • Published Online: 01 March 2016