A vertex cover of a graph $G$ is a subset of vertices $C \subseteq V(G)$ such that every edge of $G$ is incident to at least one vertex in $C$. The vertex cover number of $G$ is the minimum cardinality of a vertex cover of $G$ and is denoted by $\tau(G)$. A snark is a connected, bridgeless, cubic graph that has an edge chromatic number of four, meaning its edges cannot be properly colored with only three colors. In this work, we investigate the problem of determining the value of a minimum vertex cover for classes of snark graphs. Given a positive integer $k$, we firstly prove that determining whether an arbitrary snark has a vertex cover $C$ with size $|C| \leq k$ is an NP-complete problem. Secondly, we determine the vertex cover number $\tau(G)$ for several subclasses of snark graphs, such as Flower snarks, Goldberg snarks, Generalized Blanu\v{s}a snarks and Loupekine snarks.
A vertex cover $S\subseteq V(G)$ is called a total vertex cover of $G$ if the graph $\langle S \rangle$ induced by set $S$ does not contain isolated vertices, i.e., $ | N_G(v) \cap S | \ge 1$ for every $v \in S$. The total vertex cover number of $G$, denoted by $\beta_t(G)$, is the minimum cardinality of a total vertex...
Aziz B. Tapeing, Sergio R. Canoy· Far East Journal of Mathemat...· 0 citations
In the vertex cover interdiction problem, we are given an undirected graph $G=(V,E)$, two integers $t$ and $k$ and a vertex subset $B\subseteq V$, and we are asked to find a set $X \subseteq B$ with $|X|\leq t$ such that $X$ hits (i.e., intersects) all the vertex covers of $G$ of size at most $k$. Recently, Gr\"une and...
Takehiro Ito, Naonori Kakimura, N. Kamiyama et al.· 0 citations
A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all...
Let $G$ be a graph and $k$ be a positive integer. A total $k$-labeling of $G$ assigns to each vertex and each edge a label from $\{1,\ldots,k\}$. The weight of a vertex is the sum of its label and the labels of its incident edges. A total labeling is vertex irregular if all vertex weights are distinct. The total vertex...
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
Given a set $V$ of $n$ vertices and an integer $k\ge1$, our goal is to maximize the number of edges in graphs $G_1, G_2, \ldots, G_k$, defined on $V$, under the constraint that the union of all graphs, thought of as a multi-graph, does not contain a rainbow copy of the path $P_5$ on $5$ vertices, that is, a copy of $P_...
Sylwia Antoniuk, Andrzej Grzesik, Magdalena Prorok et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
