Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe optimal proper connection number of a graph with given independence number
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Given a digraph $D$ with $m$ arcs and a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$, we say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and no two vertices in $D$ have the same vertex-sum under $tau$, where the vertex-sum of a vertex $u$ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs, biregular bipartite graphs, and graphs with large maximum degree. In this paper, we establish more evidence for the aforementioned conjecture by studying antimagic orientations of graphs $G$ with independence number at least $|V(G)|/2$ or at most four. We obtain several results. The method we develop in this paper may shed some light on attacking the aforementioned conjecture.
Let $G$ be a finite group, the enhanced power graph of $G$, denoted by $Gamma_G^e$, is the graph with vertex set $G$ and two vertices $x,y$ are edge connected in $Gamma_{G}^e$ if there exist $zin G$ such that $x,yinlangle zrangle$. Let $zeta$ be a edge-coloring of $Gamma_G^e$. In this article, we calculate the rainbow connection number of the enhanced power graph $Gamma_G^e$.
A signed graph $(G, sigma)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $(G, sigma)$. Let $c(G)$, $alpha(G)$ and $r(G, sigma)$ be the cyclomatic number, the independence number and the rank of the adjacency matrix of $(G, sigma)$, respectively. In this paper, we study the relation among the independence number, the rank and the cyclomatic number of a signed graph $(G, sigma)$ with order $n$, and prove that $2n-2c(G) leq r(G, sigma)+2alpha(G) leq 2n$. Furthermore, the signed graphs that reaching the lower bound are investigated.
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.
Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(frac{Delta}{2}+1right)(n-1)rightrfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
