Biblio Discovery — Demo Discovery Service

2.208 hasil

Menampilkan 1–20 · 0,31 detik · RSS

Jurnal

Discrete Mathematics & Theoretical Computer Science

Scopus

ISSN 1365-8050 · Discrete Mathematics & Theoretical Computer Science · 2.208 artikel di indeks

  1. Artikel Jurnal

    Watson-Crick conjugates of words and languages

    Kalpana Mahalingam; Anuran Maity

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:3 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  2. Artikel Jurnal

    Pushing Vertices to Make Graphs Irregular

    Julien Bensmail; Clara Marcille; Mano Orenga

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:3 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  3. Artikel Jurnal

    4-tangrams are 4-avoidable

    Pascal Ochem; Théo Pierron

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:3 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  4. Artikel Jurnal

    The Price of Upwardness

    Patrizio Angelini; Therese Biedl; Markus Chimani dkk.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:3 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  5. Artikel Jurnal

    Total $k$-coalition: bounds, exact values and an application to double coalition

    Boštjan Brešar; Sandi Klavžar; Babak Samadi

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:3 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  6. Artikel Jurnal

    Spanning Trees Minimizing Branching Costs

    Luisa Gargano; Adele A. Rescigno

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Discrete Algorithms · 2025 · Inggris · DOAJ Scopus

    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…

  7. Artikel Jurnal

    From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs

    Giuseppe Di Battista; Fabrizio Frati

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  8. Artikel Jurnal

    On Separating Path and Tree Systems in Graphs

    Ahmad Biniaz; Prosenjit Bose; Jean-Lou De Carufel dkk.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  9. Artikel Jurnal

    Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs

    Lorenzo Balzotti

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Discrete Algorithms · 2025 · Inggris · DOAJ Scopus

    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…

  10. Artikel Jurnal

    Treewidth 2 in the Planar Graph Product Structure Theorem

    Marc Distel; Kevin Hendrey; Nikolai Karol dkk.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  11. Artikel Jurnal

    Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees

    Katharina T. Huber; Simone Linz; Vincent Moulton

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  12. Artikel Jurnal

    Hypergraph Representation via Axis-Aligned Point-Subspace Cover

    Oksana Firman; Joachim Spoerhase

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  13. Artikel Jurnal

    Polynomial kernels for edge modification problems towards block and strictly chordal graphs

    Maël Dumas; Anthony Perez; Mathis Rocton dkk.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Discrete Algorithms · 2025 · Inggris · DOAJ Scopus

    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…

  14. Artikel Jurnal

    A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number

    Marcin Pilipczuk; Paweł Rzążewski

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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.

  15. Artikel Jurnal

    Improved Combinatorial Approximations for Weighted Correlation Clustering

    Mojtaba Ostovari; Alireza Zarei

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Discrete Algorithms · 2025 · Inggris · DOAJ Scopus

    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…

  16. Artikel Jurnal

    On the on-line coloring of unit interval graphs with proper interval representation

    Israel R. Curbelo; Hannah R. Malko

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  17. Artikel Jurnal

    Planar cycle-extendable graphs

    Aditya Y Dalwadi; Kapil R Shenvi Pause; Ajit A Diwan dkk.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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…

  18. Artikel Jurnal

    $\mathcal{S}$-adic characterization of minimal dendric shifts

    France Gheeraert; Julien Leroy

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  19. Artikel Jurnal

    Involution factorizations of Ewens random permutations

    Charles Burnette

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Combinatorics · 2025 · Inggris · DOAJ Scopus

    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…

  20. Artikel Jurnal

    Cop-width, flip-width and strong colouring numbers

    Robert Hickingbotham

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · Inggris · DOAJ Scopus

    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.