|
|
|
|
on •-lict signed graphs l_•_c(s) and •-line signed graphs l_•(s)
|
|
|
|
|
|
|
|
نویسنده
|
acharya mukti ,jain rashmi ,kansal sangita
|
|
منبع
|
transactions on combinatorics - 2016 - دوره : 5 - شماره : 1 - صفحه:37 -48
|
|
چکیده
|
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_{vwin 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 $vin v(s)$ is a common vertex of edges $e$ and $e' $. the linecut 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 cutvertices 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 cutvertex $c$ of $g$ such that $e$ is incident with $c$. in this paper, we introduce dotlict 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 $pin v(s)$ is a common vertex of these edges, and it has the sign $mu_sigma(v)$, if $uin e(s)$ and $vin c(s)$. we characterize signed graphs on $k_p$, $pgeq2$, 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 $ssim l_{bullet_c}(s)$, $ssim 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 ,•-line signed graph ,•-lict signed graph.
|
|
آدرس
|
delhi technological university, department of applied mathematics, india, delhi technological university, department of applied mathematics, india, delhi technological university, delhi technological university,, department of applied mathematics, india
|
|
پست الکترونیکی
|
sangita_kansal15@rediffmail.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|