پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,730,714 |
| تعداد دریافت فایل اصل مقاله | 17,563,021 |
ON $\bullet$-LICT signed graohs $L_{\bullet_c}(S)$ and $\bullet$-LINE signed graohs $L_\bullet(S)$ | ||
| Transactions on Combinatorics | ||
| مقاله 4، دوره 5، شماره 1، خرداد 2016، صفحه 37-48 اصل مقاله (300.16 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2016.7890 | ||
| نویسندگان | ||
| Mukti Acharya؛ Rashmi Jain* ؛ Sangita Kansal | ||
| DELHI TECHNOLOGICAL UNIVERSITY, DELHI - INDIA | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Signed graph؛ Balance؛ Switching؛ $bullet$-line signed graph؛ $bullet$-lict signed graph | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 3,544 تعداد دریافت فایل اصل مقاله: 3,611 |
||