2.208 hasil
Menampilkan 1–20 · 0,31 detik · RSS
Discrete Mathematics & Theoretical Computer Science
Scopus
ISSN 1365-8050 · Discrete Mathematics & Theoretical Computer Science · 2.208 artikel di indeks
-
Artikel Jurnal
Watson-Crick conjugates of words and languages
In this work, we explore the concept of Watson-Crick conjugates, also known as $θ$-conjugates (where $θ$ is an antimorphic involution), of words and languages. This concept extends the classical idea of conjugates by incorporating the Watson-Crick complementarity of DNA sequences. Our investigation…
-
Artikel Jurnal
Pushing Vertices to Make Graphs Irregular
In connection with the so-called 1-2-3 Conjecture, we introduce and study a new problem related to proper labellings. In the regular problem, proper labellings of graphs are designed by assigning strictly positive labels to the edges so that any two adjacent vertices get incident to distinct sums…
-
Artikel Jurnal
4-tangrams are 4-avoidable
A tangram is a word in which every letter occurs an even number of times. Thus it can be cut into parts that can be arranged into two identical words. The \emph{cut number} of a tangram is the minimum number of required cuts in this process. Tangrams with cut number one corresponds to squares. For…
-
Artikel Jurnal
The Price of Upwardness
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a…
-
Artikel Jurnal
Total $k$-coalition: bounds, exact values and an application to double coalition
Let $G=\big{(}V(G),E(G)\big{)}$ be a graph with minimum degree $k$. A subset $S\subseteq V(G)$ is called a total $k$-dominating set if every vertex in $G$ has at least $k$ neighbors in $S$. Two disjoint sets $A,B\subset V(G)$ form a total $k$-coalition in $G$ if none of them is a total…
-
Artikel Jurnal
Spanning Trees Minimizing Branching Costs
The Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$. This problem, known to be NP-hard, has attracted significant attention due to its importance in network…
-
Artikel Jurnal
From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. In this paper, focusing on maximal plane graphs, we prove upper and lower bounds on…
-
Artikel Jurnal
On Separating Path and Tree Systems in Graphs
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating…
-
Artikel Jurnal
Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
A path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. Even if path graphs and directed path graphs are characterized very similarly, their recognition algorithms differ widely. We further unify these two graph classes…
-
Artikel Jurnal
Treewidth 2 in the Planar Graph Product Structure Theorem
We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph…
-
Artikel Jurnal
Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees
Phylogenetic networks are a special type of graph which generalize phylogenetic trees and that are used to model non-treelike evolutionary processes such as recombination and hybridization. In this paper, we consider {\em unrooted} phylogenetic networks, i.e. simple, connected graphs…
-
Artikel Jurnal
Hypergraph Representation via Axis-Aligned Point-Subspace Cover
We propose a new representation of $k$-partite, $k$-uniform hypergraphs, that is, a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short. Given positive integers $\ell, d$, and $k$ with…
-
Artikel Jurnal
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph $G = (V,E)$ and an integer $k \in \mathbb{N}$ and seeks to edit (add or delete) at most $k$ edges from $G$ to obtain a block graph or a strictly chordal graph. The completion and…
-
Artikel Jurnal
A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.
-
Artikel Jurnal
Improved Combinatorial Approximations for Weighted Correlation Clustering
We present combinatorial approximation algorithms for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices, denoting their difference and similarity. The goal is to cluster the vertices with minimum total…
-
Artikel Jurnal
On the on-line coloring of unit interval graphs with proper interval representation
We define the problem as a two-player game between Algorithm and Builder. The game is played in rounds. Each round, Builder presents an interval that is neither contained in nor contains any previously presented interval. Algorithm immediately and irrevocably assigns the interval a color that has…
-
Artikel Jurnal
Planar cycle-extendable graphs
For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs - that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as 1-extendable graphs…
-
Artikel Jurnal
$\mathcal{S}$-adic characterization of minimal dendric shifts
Dendric shifts are defined by combinatorial restrictions of the extensions of the words in their languages. This family generalizes well-known families of shifts such as Sturmian shifts, Arnoux-Rauzy shifts and codings of interval exchange transformations. It is known that any minimal dendric shift…
-
Artikel Jurnal
Involution factorizations of Ewens random permutations
An involution is a bijection that is its own inverse. Given a permutation $σ$ of $[n],$ let $\mathsf{invol}(σ)$ denote the number of ways $σ$ can be expressed as a composition of two involutions of $[n].$ We prove that the statistic $\mathsf{invol}$ is asymptotically lognormal when the symmetric…
-
Artikel Jurnal
Cop-width, flip-width and strong colouring numbers
Cop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width. In this paper, we bound the cop-width and flip-width of a graph by its strong colouring numbers. In…
Menampilkan maksimal 50 halaman. Persempit pencarian dengan filter untuk hasil yang lebih spesifik.