Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe phylogeny number in the aspect of triangles and diamonds of a graph
264
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given an acyclic digraph $D$, the competition graph of $D$, denoted by $C(D)$, is the simple graph having vertex set $V(D)$ and edge set ${uv mid (u, w), (v, w) in A(D) text{ for some } w in V(D) }$. The phylogeny graph of an acyclic digraph $D$, denoted by $P(D)$, is the graph with the vertex set $V(D)$ and the edge set $E(U(D)) cup E(C(D))$ where $U(D)$ denotes the underlying graph of $D$. The notion of phylogeny graphs was introduced by Roberts and Sheng~cite{roberts1997phylogeny} as a variant of competition graph. Moral graphs having arisen from studying Bayesian networks are the same as phylogeny graphs. In this paper, we integrate the existing theorems computing phylogeny numbers of connected graph with a small number of triangles into one proposition: for a graph $G$ containing at most two triangle, $ |E(G)|-|V(G)|-2t(G)+d(G)+1 le p(G) le |E(G)|-|V(G)|-t(G)+1 $ where $t(G)$ and $d(G)$ denote the number of triangles and the number of diamond in $G$, respectively. Then we show that these inequalities hold for graphs with many triangles. In the process of showing it, we derive a useful theorem which plays a key role in deducing various meaningful results including a theorem that answers a question given by Wu~{it et al.}~cite{Wu2019}.
rate research
Read More
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turan, Rademacher solved the first non-trivial case of this problem in 1941. The problem was revived by ErdH{o}s in 1955; it is now known as the ErdH{o}s-Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from~$1$, which in this range confirms a conjecture of Lovasz and Simonovits from 1975. Furthermore, we give a description of the extremal 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.
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.
For a fixed planar graph $H$, let $operatorname{mathbf{N}}_{mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $operatorname{mathbf{N}}_{mathcal{P}}(n,C_m)$ is currently known for $min{3,4,5,6,8}$. In this note, we extend this list by establishing $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{10})sim(n/5)^5$ and $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{12})sim(n/6)^6$. We prove this by answering the following question for $min{5,6}$, which is interesting in its own right: which probability mass $mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $mu$ form an $m$-cycle?
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
