Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let D be an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let m(G) denote the minimum number of dependent arcs over all acyclic orientations of G. For any k > 0, a generalized Mycielski graph M_k(G) of G is defined. Note that M_1(G) is the usual Mycielskian of G. We generalize results concerning m(M_1(G)) in K. L. Collins, K. Tysdal, J. Graph Theory, 46 (2004), 285-296, to m(M_k(G)). The underlying graph of a Hasse diagram is called a cover graph. Let c(G) denote the the minimum number of edges to be deleted from a graph G to get a cover graph. Analogue results about c(G) are also obtained.
rate research
Read More
We investigate the independence number of two graphs constructed from a polarity of $mathrm{PG}(2,q)$. For the first graph under consideration, the ErdH{o}s-Renyi graph $ER_q$, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper we consider the ErdH{o}s-Renyi hypergraph of triangles $mathcal{H}_q$. We determine the exact magnitude of the independence number of $mathcal{H}_q$, $q$ even. This solves a problem posed by Mubayi and Williford.
We show that the cop number of every generalized Petersen graph is at most 4. The strategy is to play a modified game of cops and robbers on an infinite cyclic covering space where the objective is to capture the robber or force the robber towards an end of the infinite graph. We prove that finite isometric subtrees are 1-guardable and apply this to determine the exact cop number of some families of generalized Petersen graphs. We also extend these ideas to prove that the cop number of any connected I-graph is at most 5.
An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. The $proper$ $connection$ $number$ of a connected graph $G$, denoted by $pc(G)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Susan A. van Aardt et al. gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note, %optimizes the boundary of the number of edges %we study the $proper$ $connection$ $number$ is under the conditions of adding the minimum degree and optimizing the number of edges. our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $kgeq3$. If $|E(G)|geq binom{n-m-(k+1-m)(delta+1)}{2} +(k+1-m)binom{delta+1}{2}+k+2$, then $pc(G)leq k$, where $m$ takes the value $t$ if $delta=1$ and $lfloor frac{k}{delta-1} rfloor$ if $deltageq2$. Furthermore, if $k=2$ and $delta=2$, %(i.e., $|E(G)|geq binom{n-5}{2} +7$) $pc(G)leq 2$, except $Gin {G_{1}, G_{n}}$ ($ngeq8$), where $G_{1}=K_{1}vee 3K_{2}$ and $G_{n}$ is obtained by taking a complete graph $K_{n-5}$ and $K_{1}vee (2K_{2}$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}vee (2K_{2}$) being joined. If $k=2$, $delta geq 3$, we conjecture $pc(G)leq 2$, where $m$ takes the value $1$ if $delta=3$ and $0$ if $deltageq4$ in the assumption.
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.
The minimum forcing number of a graph $G$ is the smallest number of edges simultaneously contained in a unique perfect matching of $G$. Zhang, Ye and Shiu cite{HDW} showed that the minimum forcing number of any fullerene graph was bounded below by $3$. However, we find that there exists exactly one excepted fullerene $F_{24}$ with the minimum forcing number $2$. In this paper, we characterize all fullerenes with the minimum forcing number $3$ by a construction approach. This also solves an open problem proposed by Zhang et al. We also find that except for $F_{24}$, all fullerenes with anti-forcing number $4$ have the minimum forcing number $3$. In particular, the nanotube fullerenes of type $(4, 2)$ are such fullerenes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
