Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-color forcing in graphs
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G=(V,E)$ be a finite connected graph along with a coloring of the vertices of $G$ using the colors in a given set $X$. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research.
rate research
Read More
Tuza [1992] proved that a graph with no cycles of length congruent to $1$ modulo $k$ is $k$-colorable. We prove that if a graph $G$ has an edge $e$ such that $G-e$ is $k$-colorable and $G$ is not, then for $2leq rleq k$, the edge $e$ lies in at least $prod_{i=1}^{r-1}(k-i)$ cycles of length $1mod r$ in $G$, and $G-e$ contains at least $frac{1}{2}prod_{i=1}^{r-1}(k-i)$ cycles of length $0 mod r$. A $(k,d)$-coloring of $G$ is a homomorphism from $G$ to the graph $K_{k:d}$ with vertex set $mathbb{Z}_{k}$ defined by making $i$ and $j$ adjacent if $dleq j-i leq k-d$. When $k$ and $d$ are relatively prime, define $s$ by $sdequiv 1mod k$. A result of Zhu [2002] implies that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $iin {1,ldots,2d-1}$. In fact, only $d$ classes need be excluded: we prove that if $G-e$ is $(k,d)$-colorable and $G$ is not, then $e$ lies in at least one cycle with length congruent to $ismod k$ for some $i$ in ${1,ldots,d}$. Furthermore, if this does not occur with $iin{1,ldots,d-1}$, then $e$ lies in at least two cycles with length $1mod k$ and $G-e$ contains a cycle of length $0 mod k$.
In this paper we compare the brushing number of a graph with the zero-forcing number of its line graph. We prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Using a similar construction, we also prove the conjecture that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph; moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight.
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.
Let $c:E(G)to [k]$ be an edge-coloring of a graph $G$, not necessarily proper. For each vertex $v$, let $bar{c}(v)=(a_1,ldots,a_k)$, where $a_i$ is the number of edges incident to $v$ with color $i$. Reorder $bar{c}(v)$ for every $v$ in $G$ in nonincreasing order to obtain $c^*(v)$, the color-blind partition of $v$. When $c^*$ induces a proper vertex coloring, that is, $c^*(u) eq c^*(v)$ for every edge $uv$ in $G$, we say that $c$ is color-blind distinguishing. The minimum $k$ for which there exists a color-blind distinguishing edge coloring $c:E(G)to [k]$ is the color-blind index of $G$, denoted $operatorname{dal}(G)$. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if $operatorname{dal}(G) leq 2$ is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when $operatorname{dal}(G)$ is finite for a class of 3-regular graphs.
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)leq F(G)leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for bipartite graphs $G$, $f(G)=n-1$ if and only if $G$ is complete bipartite graph $K_{n,n}$. In this paper, we solve the problem for general graphs and obtain that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or $K^+_{n,n}$ ($K_{n,n}$ with arbitrary additional edges in the same partite set). For a larger class of graphs $G$ with $F(G)=n-1$ we show that $G$ is $n$-connected and a brick (3-connected and bicritical graph) except for $K^+_{n,n}$. In particular, we prove that the forcing spectrum of each such graph $G$ is continued by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $lfloorfrac{n}{2}rfloor$ to $n-1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
