Zobrazeno 1 - 10
of 831
pro vyhledávání: '"Hanaka A"'
Given a graph $G$ and two spanning trees $T$ and $T'$ in $G$, Spanning Tree Reconfiguration asks whether there is a step-by-step transformation from $T$ to $T'$ such that all intermediates are also spanning trees of $G$, by exchanging an edge in $T$
Externí odkaz:
http://arxiv.org/abs/2409.07848
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
Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent $n$ selfish agents and the weight of each edge $uv$ denotes how much agent $u$ gains (or loses) when she is placed in the same
Externí odkaz:
http://arxiv.org/abs/2402.10815
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are th
Externí odkaz:
http://arxiv.org/abs/2402.09971
We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we pro
Externí odkaz:
http://arxiv.org/abs/2312.16964
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
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
Autor:
Hanaka, Tesshu, Kobayashi, Yasuaki
In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset $V_{\rm NT}$ of vertices as an internal vertex. This problem, called Minimum Weight Non-Terminal Spanning Tree, includes $s$-$t$
Externí odkaz:
http://arxiv.org/abs/2310.05494
Fractional hedonic games are coalition formation games where a player's utility is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition forma
Externí odkaz:
http://arxiv.org/abs/2310.05139
In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each position, called a game value. A game (ruleset) is called universal if any ga
Externí odkaz:
http://arxiv.org/abs/2310.01983