Source author record

Tadashi Sakuma

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.OC

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Stable structure on safe set problems in vertex-weighted graphs

Let $G$ be a graph, and let $w$ be a positive real-valued weight function on $V(G)$ . For every subset $S$ of $V(G)$ , let $w(S)=\sum_{v \in S} w(v).$ A non-empty subset $S \subset V(G)$ is a weighted safe set of $(G,w)$ if, for every component $C$ of the subgraph induced by $S$ and every component $D$ of $G-S$ , we have $w(C) \geq w(D)$ whenever there is an edge between $C$ and $D$ . If the subgraph of $G$ induced by a weighted safe set $S$ is connected, then the set $S$ is called a connected weighted safe set of $(G,w)$ . The weighted safe number $\mathrm{s}(G,w)$ and connected weighted safe number $\mathrm{cs}(G,w)$ of $(G,w)$ are the minimum weights $w(S)$ among all weighted safe sets and all connected weighted safe sets of $(G,w)$ , respectively. Note that for every pair $(G,w)$ , $\mathrm{s}(G,w) \le \mathrm{cs}(G,w)$ by their definitions. Recently, it was asked which pair $(G,w)$ satisfies the equality and shown that every weighted cycle satisfies the equality. In this paper, we give a complete list of connected bipartite graphs $G$ such that $\mathrm{s}(G,w)=\mathrm{cs}(G,w)$ for every weight function $w$ on $V(G)$ .

preprint2014arXiv

On the balanced decomposition number

A {\em balanced coloring} of a graph $G$ means a triple $\{P_1,P_2,X\}$ of mutually disjoint subsets of the vertex-set $V(G)$ such that $V(G)=P_1 \uplus P_2 \uplus X$ and $|P_1|=|P_2|$ . A {\em balanced decomposition} associated with the balanced coloring $V(G)=P_1 \uplus P_2 \uplus X$ of $G$ is defined as a partition of $V(G)=V_1 \uplus \cdots \uplus V_r$ (for some $r$ ) such that, for every $i \in \{1,\cdots,r\}$ , the subgraph $G[V_i]$ of $G$ is connected and $|V_i \cap P_1| = |V_i \cap P_2|$ . Then the {\em balanced decomposition number} of a graph $G$ is defined as the minimum integer $s$ such that, for every balanced coloring $V(G)=P_1 \uplus P_2 \uplus X$ of $G$ , there exists a balanced decomposition $V(G)=V_1 \uplus \cdots \uplus V_r$ whose every element $V_i (i=1, \cdots, r)$ has at most $s$ vertices. S. Fujita and H. Liu [\/SIAM J. Discrete Math. 24, (2010), pp. 1597--1616\/] proved a nice theorem which states that the balanced decomposition number of a graph $G$ is at most $3$ if and only if $G$ is $\lfloor\frac{|V(G)|}{2}\rfloor$ -connected. Unfortunately, their proof is lengthy (about 10 pages) and complicated. Here we give an immediate proof of the theorem. This proof makes clear a relationship between balanced decomposition number and graph matching.

preprint2012arXiv

Agent Arrangement Problem

An {\em arrangement} of an ordered pair $(G_A, G_M)$ of graphs is defined as a function $f$ from $V(G_A)$ to $V(G_M)$ such that, for each vertex $c$ of $G_M$ , the vertex-set $f^{-1}(c)$ of $G_A$ either is $\emptyset$ (the case when $c \not\in f(V(G_A))$ ) or induces a connected subgraph of $G_A$ and that the family $\{f^{-1}(y) : y \in V(G_M), f^{-1}(y) \neq \emptyset\}$ is a partition of $V(G_A)$ . Let $f$ be an arrangement of $(G_A, G_M)$ , let $pq$ be an edge of $G_M$ and let $U$ be a subset of $f^{-1}(p)$ such that each of the three graphs $G_A[U]$ , $G_A[f^{-1}(p)\setminus U]$ and $G_A[f^{-1}(q)\cup U]$ is ether connected or $\emptyset$ and that $\big(f^{-1}(p)\cup f^{-1}(q) \big) \setminus U \neq \emptyset$ . A {\em transfer} of $U$ from $p$ to $q$ is defined as the modification $f^{\prime}$ of $f$ such that $f^{\prime}(x):=f(x)$ for every $x \notin U$ and $f^{\prime}(u):=q$ for every $u \in U$ . Two arrangements $f$ and $g$ of $(G_A, G_M)$ are called {\em t-equivalent} if they can be transformed into each other by a finite sequence of transfers. An ordered pair $(G_A, G_M)$ of graphs is called {\em almighty} if every two arrangements of the pair $(G_A, G_M)$ are t-equivalent. In this study, we consider the following two decision problems. [{\bf (P1)}]{For a given pair of arrangements $f$ and $g$ of a given ordered pair $(G_A,G_M)$ of graphs, decide whether $f$ is t-equivalent to $g$ or not.} [{\bf (P2)}]{For a given ordered pair $(G_A,G_M)$ of graphs, decide whether the pair $(G_A,G_M)$ is almighty or not.} We show an $\Od(|E(G_A)|+(|V(G_M)|+|E(G_A)|)|V(G_A)|)$-time algorithm for {\bf (P1)}, and prove the $\co\np$-completeness of {\bf (P2)}.

preprint2012arXiv

On ideal minimally non-packing clutters

We consider the following conjecture proposed by Cornuéjols, Guenin and Margot: every ideal minimally non-packing clutter has a transversal of size 2. For a clutter C, the tilde clutter is the set of hyperedges of C which intersect any minimum transversal in exactly one element. We divide the (non-)existence problem of an ideal minimally non-packing clutter D into two steps. In the first step, we give necessary conditions for C = the tilde clutter of D when a clutter D is an ideal minimally non-packing clutter. In the second step, for a clutter C satisfying the conditions in the first step, we consider whether C has an ideal minimally non-packing clutter D with C= the tilde clutter of D. We show that the clutter of a combinatorial affine plane satisfies the conditions in the first step. Moreover, we show that the clutter of a combinatorial affine plane does not have any ideal minimally non-packing clutter of blocking number at least 3.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.