Zobrazeno 1 - 10
of 33
pro vyhledávání: '"Gima, Tatsuya"'
We show that for every $n$-vertex graph with at least one edge, its treewidth is greater than or equal to $n \lambda_{2} / (\Delta + \lambda_{2}) - 1$, where $\Delta$ and $\lambda_{2}$ are the maximum degree and the second smallest Laplacian eigenval
Externí odkaz:
http://arxiv.org/abs/2404.08520
Autor:
Gima, Tatsuya, Hanaka, Tesshu, Kobayashi, Yasuaki, Otachi, Yota, Shirai, Tomohito, Suzuki, Akira, Tamura, Yuma, Zhou, Xiao
The problem of packing as many subgraphs isomorphic to $H \in \mathcal H$ as possible in a graph for a class $\mathcal H$ of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for $H$
Externí odkaz:
http://arxiv.org/abs/2312.08639
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the problem is polynomial-time solvable on K\H{o}nig-Egerv\'{a}ry graphs (an
Externí odkaz:
http://arxiv.org/abs/2311.13132
The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected component
Externí odkaz:
http://arxiv.org/abs/2311.05892
The problem of determining whether a graph $G$ contains another graph $H$ as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph algorithms. While it is NP-complete when $G$ and $H$ are general graphs
Externí odkaz:
http://arxiv.org/abs/2311.03225
Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-complete problem, known to rem
Externí odkaz:
http://arxiv.org/abs/2309.17204
In a vertex-colored graph $G = (V, E)$, a subset $S \subseteq V$ is said to be consistent if every vertex has a nearest neighbor in $S$ with the same color. The problem of computing a minimum cardinality consistent subset of a graph is known to be NP
Externí odkaz:
http://arxiv.org/abs/2305.07259
Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting,
Externí odkaz:
http://arxiv.org/abs/2207.01024
Publikováno v:
In Theoretical Computer Science 12 February 2025 1026
Publikováno v:
In Theoretical Computer Science 12 January 2025 1024