Search

We study the (a, b)-monochromatic transversal game that is a combinatorial Maker–Breaker game where Alice and Bob alternately colour a vertices in red and b vertices in blue of a hypergraph, respectively. Either player is enabled to start the game. Alice tries to construct a hyperedge transversal, and Bob tries to prevent this. The winner is Alice if she obtains a red hyperedge transversal; otherwise, Bob wins the game if he obtains a monochromatic blue hyperedge. Maker–Breaker games were determined to be PSPACE-complete. In this work, we analyze the game played on clique-hypergraphs of powers of cycles, and we show strategies that, depending on the choice of the parameters, allow a specific player to win the game. [ABSTRACT FROM AUTHOR]

A graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that each edge is uniquely identified by the absolute difference of the labels of its endpoints. In this work, we study the graceful labeling problem in the context of maker-breaker graph games. The Graceful Game was introduced by Tuza, in 2017, as a two-players game on a connected graph in which the players, Alice and Bob, take moves labeling the vertices with distinct integers from 0 to m. Players are constrained to use only legal labelings (moves), that is, after a move, all edge labels are distinct. Alice's goal is to obtain a graceful labeling for the graph, as Bob's goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in graph classes: paths, complete graphs, cycles, complete bipartite graphs, caterpillars, trees, gear graphs, web graphs, prisms, hypercubes, 2-powers of paths, wheels and fan graphs. [ABSTRACT FROM AUTHOR]

For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer k, the recognition of the connected K4-free graphs G with yR(G) − yr2(G) = k is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs G such that yr2(H) = yR(H) for every induced subgraph H of G, and collect several properties of the graphs G with R(G) = 3/2yr2(G).

Snarks are cyclically 4-edge-connected cubic graphs that admit no proper 3-edge-coloring. A snark is of Type 1 if it has a proper total coloring of its vertices and edges with four colors; it is of Type 2 if any total coloring requires at least five colors. Following an extensive computer search, in 2003, Cavicchioli et al. asked whether there exist Type 2 snarks of girth at least 5. This question is still open, however, in 2015, Brinkmann et al. described the first known family of Type 2 snarks of girth 4. In this work we provide new families of Type 2 snarks of girth 4, all of which can be constructed by a dot product of two Type 1 snarks. We also show that the previously constructed Type 2 snarks of Brinkmann et al. do not have this property. Keywords: dot product, total coloring, snark. [ABSTRACT FROM AUTHOR]

We show that all members of the SemiBlowup, Blowup and the first Loupekine snark families have equitable total chromatic number equal to 4. These results provide evidence of negative answers for the questions proposed: by (A. Cavicchioli, T.E. Murgolo, B. Ruini and F. Spaggiari, Acta Appl. Math.76 (2003) 56–88.) about the smallest order of a Type 2 snark of girth at least 5; and by (S. Dantas, C.M.H. De Figueiredo, G. Mazzuoccolo, M. Preissmann, V.F. dos Santos and D. Sasaki, Discret. Appl. Math.209 (2016) 84–91.) about the existence of Type 1 cubic graph with girth at least 5 and equitable total chromatic number 5. Moreover, we show new infinite families of snarks obtained by the Kochol superpositions that are Type 1. [ABSTRACT FROM AUTHOR]

The coloring game is played by Alice and Bob on a finite graph G. They take turns properly coloring the vertices with t colors. The goal of Alice is to color the input graph with t colors, and Bob does his best to prevent it. If at any point there exists an uncolored vertex without available color, then Bob wins; otherwise Alice wins. The game chromatic number χg(G) of G is the smallest number t such that Alice has a winning strategy. In 1991, Bodlaender showed the smallest tree T with χg(T) equal to 4, and in 1993 Faigle et al. proved that every tree T satisfies the upper bound χg(T)≤4. The stars T = K1,p with p ≥ 1 are the only trees satisfying χg(T) = 2; and the paths T = Pn, n ≥ 4, satisfy χg(T) = 3. Despite the vast literature in this area, there does not exist a characterization of trees with χg(T) = 3 or 4. We answer a question about the required degree to ensure χg(T) = 4, by exhibiting infinitely many trees with maximum degree 3 and game chromatic number 4. [ABSTRACT FROM AUTHOR]

Abstract Background The double-cut-and-join (DCJ) is a model that is able to efficiently sort a genome into another, generalizing the typical mutations (inversions, fusions, fissions, translocations) to which genomes are subject, but allowing the existence of circular chromosomes at the intermediate steps. In the general model many circular chromosomes can coexist in some intermediate step. However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation. These two consecutive DCJ operations, which create and reincorporate a circular chromosome, mimic a transposition or a block-interchange. When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model. If the genomes have unequal contents, in addition to DCJ it is necessary to consider indels, which are insertions and deletions of DNA segments. Linear time algorithms were proposed to compute the distance and to find a sorting scenario in a general, unrestricted DCJ-indel model that considers DCJ and indels. Results In the present work we consider the restricted DCJ-indel model for sorting linear genomes with unequal contents. We allow DCJ operations and indels with the following constraint: if a circular chromosome is created by a DCJ, it has to be reincorporated in the next step (no other DCJ or indel can be applied between the creation and the reincorporation of a circular chromosome). We then develop a sorting algorithm and give a tight upper bound for the restricted DCJ-indel distance. Conclusions We have given a tight upper bound for the restricted DCJ-indel distance. The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.

Abstract A seminal result by Nordhaus and Gaddum states that 2 n ≤ χ (G) + χ (G ¯) ≤ n + 1 for every graph G of order n , where G ¯ is the complement of G and χ is the chromatic number. We study similar inequalities for χ g (G) and c o l g (G) , which denote, respectively, the game chromatic number and the game coloring number of G. Those graph invariants give the score for, respectively, the coloring and marking games on G when both players use their best strategies. [ABSTRACT FROM AUTHOR]

Abstract: Let G = ( V , E ) be a finite, simple, and connected graph. The closed interval I [ S ] of a set S ⊆ V is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if I [ S ] = V. The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour C t ( G ) of G is the set formed by the contour vertices of G. We consider two problems: ( a ) the problem of determining whether the contour of a graph class is geodetic; ( b ) the problem of determining if there exists a graph such that I [ C t ( G ) ] is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem ( a ) and show two infinite families such that C t ( G ) is not geodetic. Using computational tools, we establish the minimum graphs for which C t ( G ) is not geodetic; and show that all graphs with | V | < 13, and all bipartite graphs with | V | < 18, are such that I [ C t ( G ) ] is geodetic. [ABSTRACT FROM AUTHOR]

Abstract: For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most n / 3. Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most 2 n / 5 unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set H k of graphs of order at least 4 k + 4 and at most 4 k 2 − 2 k such that every maximal outerplanar graph G of order n at least 2 k + 1 that does not belong to H k has a dominating set D of order at most ⌊ k n 2 k + 1 ⌋ such that every component of the subgraph G [ D ] of G induced by D has order at least k. [ABSTRACT FROM AUTHOR]

Motivation: The traditional view of cancer evolution states that a cancer genome accumulates a sequential ordering of mutations over a long period of time. However, in recent years it has been suggested that a cancer genome may instead undergo a one-time catastrophic event, such as chromothripsis, where a large number of mutations instead occur simultaneously. A number of potential signatures of chromothripsis have been proposed. In this work, we provide a rigorous formulation and analysis of the ‘ability to walk the derivative chromosome’ signature originally proposed by Korbel and Campbell. In particular, we show that this signature, as originally envisioned, may not always be present in a chromothripsis genome and we provide a precise quantification of under what circumstances it would be present. We also propose a variation on this signature, the H/T alternating fraction, which allows us to overcome some of the limitations of the original signature. Results: We apply our measure to both simulated data and a previously analyzed real cancer dataset and find that the H/T alternating fraction may provide useful signal for distinguishing genomes having acquired mutations simultaneously from those acquired in a sequential fashion. [ABSTRACT FROM AUTHOR]

A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph [ABSTRACT FROM AUTHOR]

As a common generalization of the domination number and the total domination number of a graph G , we study the k -component domination number γ k ( G ) of G defined as the minimum cardinality of a dominating set D of G for which each component of the subgraph G [ D ] of G induced by D has order at least k . We show that for every positive integer k , and every graph G of order n at least k + 1 and without isolated vertices, we have γ k ( G ) ≤ k n k + 1 . Furthermore, we characterize all extremal graphs. We propose two conjectures concerning graphs of minimum degree 2 , and prove a related result. [ABSTRACT FROM AUTHOR]