Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA graph minors characterization of signed graphs whose signed Colin de Verdi`ere parameter $ u$ is two
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,...,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges even. By $S(G,Sigma)$ we denote the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameter $ u(G,Sigma)$ of a signed graph $(G,Sigma)$ is the largest nullity of any positive semidefinite matrix $Ain S(G,Sigma)$ that has the Strong Arnold Property. By $K_3^=$ we denote the signed graph obtained from $(K_3,emptyset)$ by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph $(G,Sigma)$ has $ u(G,Sigma)leq 2$ if and only if $(G,Sigma)$ has no minor isomorphic to $(K_4,E(K_4))$ or $K_3^=$.
rate research
Read More
Let $G$ be a graph. For a subset $X$ of $V(G)$, the switching $sigma$ of $G$ is the signed graph $G^{sigma}$ obtained from $G$ by reversing the signs of all edges between $X$ and $V(G)setminus X$. Let $A(G^{sigma})$ be the adjacency matrix of $G^{sigma}$. An eigenvalue of $A(G^{sigma})$ is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let $S_{n,k}$ be the graph obtained from the complete graph $K_{n-r}$ by attaching $r$ pendent edges at some vertex of $K_{n-r}$. In this paper we prove that there exists a switching $sigma$ such that all eigenvalues of $G^{sigma}$ are main when $G$ is a complete multipartite graph, or $G$ is a harmonic tree, or $G$ is $S_{n,k}$. These results partly confirm a conjecture of Akbari et al.
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,...,n}$ and $Sigmasubseteq E$. By $S(G,Sigma)$ we denote the set of all symmetric $Vtimes V$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The stable inertia set of a signed graph $(G,Sigma)$ is the set of all pairs $(p,q)$ for which there exists a matrix $Ain S(G,Sigma)$ with $p$ positive and $q$ negative eigenvalues which has the Strong Arnold Property. In this paper, we study the stable inertia set of (signed) graphs.
In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $phicolon V(G)to mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $phi(u)$ is different from the colour $sigma(uv)phi(v)$, where is $sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavskys research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs.
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma)$ we denote the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are adjacent and connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are adjacent and connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameters $M(G,Sigma)$ and $xi(G,Sigma)$ of a signed graph $(G,Sigma)$ are the largest nullity of any matrix $Ain S(G,Sigma)$ and the largest nullity of any matrix $Ain S(G,Sigma)$ that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 1$ and of signed graphs with $xi(G,Sigma)leq 1$. In this paper, we characterize the $2$-connected signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 2$ and the $2$-connected signed graphs $(G,Sigma)$ with $xi(G,Sigma)leq 2$.
A signed graph is a pair $(G, sigma)$, where $G$ is a graph and $sigma: E(G) to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs. Given a signed graph $(G, sigma)$ a circular $r$-coloring of $(G, sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $chi_c(G, sigma)$ of a signed graph $(G, sigma)$ is the infimum of those $r$ for which $(G, sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $max{chi_c(G, sigma): sigma text{ is a signature of $G$}}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $chi_c(G, sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
