Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe number of equivalent realisations of a rigid graph
98
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a rigid realisation of a graph $G$ in ${mathbb R}^2$, it is an open problem to determine the maximum number of pairwise non-congruent realisations which have the same edge lengths as the given realisation. This problem can be restated as finding the number of solutions of a related system of quadratic equations and in this context it is natural to consider the number of solutions in ${mathbb C}^2$ rather that ${mathbb R}^2$. We show that the number of complex solutions, $c(G)$, is the same for all generic realisations of a rigid graph $G$, characterise the graphs $G$ for which $c(G)=1$, and show that the problem of determining $c(G)$ can be reduced to the case when $G$ is $3$-connected and has no non-trivial $3$-edge-cuts. We consider the effect of the Henneberg moves and the vertex-splitting operation on $c(G)$. We use our results to determine $c(G)$ exactly for two important families of graphs, and show that the graphs in both families have $c(G)$ pairwise equivalent generic real realisations. We also show that every planar isostatic graph on $n$ vertices has at least $2^{n-3}$ pairwise equivalent real realisations.
rate research
Read More
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.
An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${mathrm{pc}_{mathrm{opt}}}(G)$ for a monochromatic connected graph $G$, to make a connected graph properly connected efficiently. More precisely, ${mathrm{pc}_{mathrm{opt}}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${mathrm{pc}_{mathrm{opt}}}(G)$ has an upper bound in terms of the independence number $alpha(G)$. Namely, we prove that for a connected graph $G$, ${mathrm{pc}_{mathrm{opt}}}(G)le frac{5alpha(G)-1}{2}$. Moreoevr, for the case $alpha(G)leq 3$, we improve the upper bound to $4$, which is tight.
It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded as a function of the genus of the graph $g(G)$. The best known bound, that $c(G) leq leftlfloor frac{3 g(G)}{2}rightrfloor + 3$, was given by Schr{o}der, who conjectured that in fact $c(G) leq g(G) + 3$. We give the first improvement to Schr{o}ders bound, showing that $c(G) leq frac{4g(G)}{3} + frac{10}{3}$.
Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with $n$ vertices, $ngeq 5$. It has been shown that the bound is sharp for $n = 5,12$ and $ngeq 14$ vertices. However, it was only conjectured by the authors about the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note we confirm their conjecture.
Let $f(n,H)$ denote the maximum number of copies of $H$ possible in an $n$-vertex planar graph. The function $f(n,H)$ has been determined when $H$ is a cycle of length $3$ or $4$ by Hakimi and Schmeichel and when $H$ is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determine $f(n,H)$ exactly in the case when $H$ is a path of length 3.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
