Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralizing Kirchhoff laws for Signed Graphs
53
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Kirchhoff-type Laws for signed graphs are characterized by generalizing transpedances through the incidence-oriented structure of bidirected graphs. The classical $2$-arborescence interpretation of Tutte is shown to be equivalent to single-element Boolean classes of reduced incidence-based cycle covers, called contributors. A generalized contributor-transpedance is introduced using entire Boolean classes that naturally cancel in a graph; classical conservation is proven to be property of the trivial Boolean classes. The contributor-transpedances on signed graphs are shown to produce non-conservative Kirchhoff-type Laws, where every contributor possesses the unique source-sink path property. Finally, the maximum value of a contributor-transpedance is calculated through the signless Laplacian.
rate research
Read More
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of allowed images, to a fixed target signed graph $(H,pi)$. The complexity of the similar homomorphism problem without lists (corresponding to all lists being $L(v)=V(H)$) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when $H$ is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and we illustrate this by classifying the complexity of irreflexive signed graphs in which the unicoloured edges form some simple structures, namely paths or cycles. The structure of the signed graphs in the polynomial cases is interesting, suggesting they may constitute a nice class of signed graphs analogous to the so-called bi-arc graphs (which characterized the polynomial cases of list homomorphisms to unsigned graphs).
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.
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.
We introduce a family of multi-way Cheeger-type constants ${h_k^{sigma}, k=1,2,ldots, n}$ on a signed graph $Gamma=(G,sigma)$ such that $h_k^{sigma}=0$ if and only if $Gamma$ has $k$ balanced connected components. These constants are switching invariant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, those measures of bipartiteness introduced by Desai-Rao, Trevisan, Bauer-Jost, respectively, on unsigned graphs,, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their correspondi
Let $mathcal G$ be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all {em connected} graphs in $mathcal G$ on $n$ vertices, and the convergence law in MSO holds if we draw uniformly at random from all graphs in $mathcal G$ on $n$ vertices. We also prove analogues of these results for the class of graphs embeddable on a fixed surface, provided we restrict attention to first order logic (FO). Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface $S$. We also prove that the closure of the set of limiting probabilities is always the finite union of at least two disjoint intervals, and that it is the same for FO and MSO. For the classes of forests and planar graphs we are able to determine the closure of the set of limiting probabilities precisely. For planar graphs it consists of exactly 108 intervals, each of length $approx 5cdot 10^{-6}$. Finally, we analyse examples of non-addable classes where the behaviour is quite different. For instance, the zero-one law does not hold for the random caterpillar on $n$ vertices, even in FO.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
