On Lict sigraphs

Document Type: Research Paper

Authors

1 University of Mysore

2 Mangalore University

Abstract

A signed graph (marked graph) is an ordered pair $S=(G,\sigma)$‎ ‎$(S=(G,\mu))$‎, ‎where $G=(V,E)$ is a graph called the underlying‎ ‎graph of $S$ and $\sigma:E\rightarrow\{+,-\}$‎ ‎$(\mu:V\rightarrow\{+,-\})$ is a function‎. ‎For a graph $G$‎, ‎$V(G)‎, ‎E(G)$ and $C(G)$ denote its vertex set‎, ‎edge set and cut-vertex‎ ‎set‎, ‎respectively‎. ‎The lict graph $L_{c}(G)$ of a graph $G=(V,E)$‎ ‎is defined as the graph having vertex set  $E(G)\cup C(G)$ in which‎ ‎two vertices are adjacent if and only if they correspond to‎ ‎adjacent edges of $G$ or one corresponds to an edge $e_{i}$ of $G$‎ ‎and the other corresponds to a cut-vertex $c_{j}$ of $G$ such that‎ ‎$e_{i}$ is incident with $c_{j}$‎. ‎In this paper‎, ‎we introduce lict‎ ‎sigraphs‎, ‎as a natural extension of the notion of lict graph to‎ ‎the realm of signed graphs‎. ‎We show that every lict sigraph is‎ ‎balanced‎. ‎We characterize signed graphs $S$ and $S^{'}$ for which‎ ‎$S\sim L_{c}(S)$‎, ‎$\eta(S)\sim L_{c}(S)$‎, ‎$L(S)\sim L_{c}(S')$‎, ‎$J(S)\sim L_{c}(S^{'})$ and $T_{1}(S)\sim L_{c}(S^{'})$‎, ‎where‎ ‎$\eta(S)$‎, ‎$L(S)$‎, ‎$J(S)$ and $T_{1}(S)$ are negation‎, ‎line graph‎, ‎jump graph and semitotal line sigraph of $S$‎, ‎respectively‎, ‎and‎ ‎$\sim$ means switching equivalence‎.

Keywords

Main Subjects


R‎. ‎P‎. ‎Abelson and M‎. ‎J‎. ‎Rosenberg (1958). ‎Symbolic Psychologic‎: ‎A model of attitudinal cognition. Behav‎. ‎Sci.. 3, 1-13
M‎. ‎Acharya (2009). $times$-line Signed Graphs. J‎. ‎Combin‎. ‎Math‎. ‎Combin‎. ‎Comput.. 69, 103-111
M‎. ‎Acharya and D‎. ‎Sinha (2003). ‎A characterization of signed graphs that are switching equivalent to their jump sigraphs. ‎Graph Theory Notes of New York. XLIV, 30-34
L‎. ‎W‎. ‎Beineke and F‎. ‎Harary (1978). ‎Consistency in marked graphs. J‎. ‎Math‎. ‎Psychol.. 18 (3), 260-269
B‎. ‎Basavanagoud and Veena N‎. ‎Mathad (2005). ‎Graph equations for line graphs‎, ‎jump graphs‎, ‎middle graphs‎, ‎litact graphs and lict graphs. Acta Cienc‎. ‎Indica Math.. 31 (3), 735-740
G‎. ‎Chartrand‎, ‎H‎. ‎Hevia‎, ‎E‎. ‎B‎. ‎Jarrett and M‎. ‎Schultz (1997). ‎Subgraph distance in graphs defined by edge transfers. ‎Discrete Math.. 170, 63-79
D‎. ‎Sinha and P‎. ‎Garg (2011). Characterization of Total Signed Graph and Semi-total Signed Graphs. Int‎. ‎J‎. ‎Contemp‎. ‎Math‎. ‎Sci.. 6 (5), 221-228
F‎. ‎Harary (1969). Graph Theory. ‎Addison-Wesley Publishing Co.‎, ‎Reading‎, ‎Mass.-Menlo Park‎, ‎Calif.-London.
F‎. ‎Harary (1953-54). ‎On the notion of balance of a signed graph. Michigan Math‎. ‎J.. 2, 143-146
F‎. ‎Harary (1957). ‎Structural duality. Behavioral Sci.. 2 (4), 255-265
V‎. ‎R‎. ‎Kulli and M‎. ‎H‎. ‎Muddebihal (2006). ‎The Lict graph and litact graph of a graph. J‎. ‎of Analysis and Comput.. 2 (1), 33-43
E‎. ‎Sampathkumar (1984). ‎Point signed and line signed graphs. Nat‎. ‎Acad‎. ‎Sci‎. ‎Lett.. 7 (3), 91-93
E‎. ‎Sampathkumar and S‎. ‎B‎. ‎Chikkodimath (1973). ‎Semitotal graphs of a graph-II. J‎. ‎Karnatak Univ‎. ‎Sci.. 18, 281-284
T‎. ‎Sozansky (1980). ‎Enumeration of weak isomorphism classes of signed graphs. J‎. ‎Graph Theory. 4 (2), 127-144
T‎. ‎Zaslavski (1998). ‎A mathematical bibliography of signed and gain graphs and its allied areas. Electronic J‎. ‎Combin.. 8 (1)
T‎. ‎Zaslavski (1982). ‎Signed graphs. Discrete Appl‎. ‎Math.. 4 (1), 47-74