It is well known that the treewidth of a graph G corresponds to the node search number where a team of searchers is pursuing a fugitive that is lazy and invisible (or alternatively is agile and ...visible) and has the ability to move with infinite speed via unguarded paths. Recently, monotone and connected node search strategies have been considered. A search strategy is monotone if it prevents the fugitive from pervading again areas from where he had been expelled and is connected if, at each step, the set of vertices that is or has been occupied by the searchers induces a connected subgraph of G. It has been shown that the corresponding connected and monotone search number of a graph G can be expressed as the connected treewidth, denoted by ctw(G), that is defined as the minimum width of a rooted tree-decomposition (X,T,r), where the union of the bags corresponding to the nodes of a path of T containing the root r is connected in G. In this paper, we initiate the algorithmic study of connected treewidth. We design a O(n2⋅logn)-time dynamic programming algorithm to compute the connected treewidth of biconnected series–parallel graphs. At the price of an extra n factor in the running time, our algorithm generalizes to graphs of treewidth at most two.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The canonical decomposition of a bipartite graph is a new decomposition method that involves three operators: parallel, series, and K⨁ S. The class of weak-bisplit graphs is the class of totally ...decomposable graphs with respect to these operators, and the class of bicographs is the class of totally decomposable graphs with respect to parallel and series operators. We prove in this paper that the class of bipartite (P6,C6)-free graphs is the class of bipartite graphs that are totally decomposable with respect to parallel and K⨁S operators. We present a linear time recognition algorithm for (P6,C6)-free graphs that is symmetrical to the linear recognition algorithms of weak-bisplit graphs and star1,2,3-free bipartite graphs. As a result of this algorithm, we present efficient solutions in this class of graphs for two optimization graph problems: the maximum balanced biclique problem and the maximum independent set problem.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
A graph
G has a
C
k‐decomposition if its edge set can be partitioned into cycles of length
k. We show that if
δ
(
G
)
≥
2
∣
G
∣
∕
3
−
1, then
G has a
C
4‐decomposition, and if
δ
(
G
)
≥
∣
G
∣
∕
2, ...then
G has a
C
2
k‐decomposition, where
k
∈
N and
k
≥
4 (we assume
G is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, Kühn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when
G is bipartite or satisfies certain expansion properties.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
The dag-width of directed graphs Berwanger, Dietmar; Dawar, Anuj; Hunter, Paul ...
Journal of combinatorial theory. Series B,
July 2012, 2012-07-00, Volume:
102, Issue:
4
Journal Article
Peer reviewed
Open access
Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm design. Tree-width can be ...characterised by a graph searching game where a number of cops attempt to capture a robber. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure, called dag-width, that can be seen to describe how close a directed graph is to a directed acyclic graph (dag). We also provide an associated decomposition and show how it is useful for developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded dag-width. We also consider the relationship between dag-width and other connectivity measures such as directed tree-width and path-width. A consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded dag-width.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Six-cycle systems Meszka, Mariusz; Rosa, Alexander
Mathematica Slovaca,
06/2021, Volume:
71, Issue:
3
Journal Article
Peer reviewed
In this article, we attempt to survey all that has been written about 6-cycle systems. In addition, several new results, including many enumeration results, are included here for the first time. Our ...survey concludes with a list of open problems.
A k‐cycle with a pendant edge attached to each vertex is called a k‐sun. The existence problem for k‐sun decompositions of Kv, with k odd, has been solved only when k = 3 or 5. By adapting a method ...used by Hoffmann, Lindner, and Rodger to reduce the spectrum problem for odd cycle systems of the complete graph, we show that if there is a k‐sun system of Kv (k odd) whenever v lies in the range 2k<v<6k and satisfies the obvious necessary conditions, then such a system exists for every admissible v≥6k. Furthermore, we give a complete solution whenever k is an odd prime.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a ...monochromatic graph isomorphic to H. Let ϕk(n,H) be the smallest number ϕ such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H‐decomposition with at most ϕ parts. Here, we study the function ϕk(n,Kr) for k≥2 and r≥3.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
For each r≥4, we show that any graph G with minimum degree at least (1−1/(100r))|G| has a fractional Kr‐decomposition. This improves the best previous bounds on the minimum degree required to ...guarantee a fractional Kr‐decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery, and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery, and Osthus, this shows that, for any graph F with chromatic number χ(F)≥4, and any ε>0, any sufficiently large graph G with minimum degree at least (1−1/(100χ(F))+ε)|G| has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
A decomposition of a graph G into isomorphic copies of a graph H is H-magic if there is a bijection f:V(G)∪E(G)→{0,1,…,|V(G)|+|E(G)|−1} such that the sum of labels of edges and vertices of each copy ...of H in the decomposition is constant. It is known that complete graphs do not admit K2-magic decompositions for n>6. By using the results on the sumset partition problem, we show that the complete graph K2m+1 admits T-magic decompositions by any graceful tree with m edges. We address analogous problems for complete bipartite graphs and for antimagic and (a,d)-antimagic decompositions.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this paper, we consider factorizations of complete graph $K_v$ into cycles and $1$--factors. We will focus on the existence of factorizations of $K_v$ containing two nonisomorphic factors. We ...obtain all possible solutions for uniform factors involving $m$--cycles and $1$--factors with a few possible exceptions when $m$ is odd.
PDF
