Source author record

Michitaka Furuya

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

10works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

A continuous generalization of domination-like invariants

In this paper, we define a new domination-like invariant of graphs. Let $\mathbb{R}^{+}$ be the set of non-negative numbers. Let $c\in \mathbb{R}^{+}-\{0\}$ be a number, and let $G$ be a graph. A function $f:V(G)\rightarrow \mathbb{R}^{+}$ is a $c$ -self-dominating function of $G$ if for every $u\in V(G)$ , $f(u)\geq c$ or $\max\{f(v):v\in N_{G}(u)\}\geq 1$ . The $c$ -self-domination number $γ^{c}(G)$ of $G$ is defined as $γ^{c}(G):=\min\{\sum_{u\in V(G)}f(u):f$ is a $c$ -self-dominating function of $G\}$ . Then $γ^{1}(G)$ , $γ^{\infty }(G)$ and $γ^{\frac{1}{2}}(G)$ are equal to the domination number, the total domination number and the half of the Roman domination number of $G$ , respectively. Our main aim is to continuously fill in the gaps among such three invariants. In this paper, we give a sharp upper bound of the $c$ -self-domination number for all $c\geq \frac{1}{2}$ .

preprint2020arXiv

The uniqueness of covers for widely generalized line graphs

As a natural generalization of line graphs, Hoffman line graphs were defined by Woo and Neumaier. Especially, Hoffman line graphs are closely related to the smallest eigenvalue of graphs, and the uniqueness of strict covers of a Hoffman line graph plays a key role in such a study. In this paper, we prove a theorem for the uniqueness of strict covers under a condition which can be checked in finite time. Our result gives a generalization and a short proof for the main part of [Ars Math.~Contemp. \textbf{1} (2008) 81--98].

preprint2016arXiv

A characterization of domination weak bicritical graphs with large diameter

The domination number of a graph $G$ , denoted by $γ(G)$ , is the minimum cardinality of a dominating set of $G$ . A vertex of a graph is called critical if its deletion decreases the domination number, and a graph is called critical if its all vertices are critical. A graph $G$ is called weak bicritical if for every non-critical vertex $x\in V(G)$ , $G-x$ is a critical graph with $γ(G-x)=γ(G)$ . In this paper, we characterize the connected weak bicritical graphs $G$ whose diameter is exactly $2γ(G)-2$ . This is a generalization of some known results concerning the diameter of graphs with a domination-criticality.

preprint2015arXiv

A New Approach Towards a Conjecture on Intersecting Three Longest Paths

In 1966, T. Gallai asked whether every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and many work has been done in this topic. One important open question in this area is to ask whether any three longest paths contains a common vertex in a connected graph. It was conjectured that the answer to this question is positive. In this paper, we propose a new approach in view of distances among longest paths in a connected graph, and give a substantial progress towards the conjecture along the idea.

preprint2015arXiv

Difference of forbidden pairs containing a claw

When we study forbidden subgraph conditions guaranteeing graphs to have some properties, a claw (or $K_{1,3}$ ) frequently appears as one of forbidden subgraphs. Recently, Furuya and Tsuchiya compared two classes generated by different forbidden pairs containing a claw, and characterized one of such classes. In this paper, we give such characterization for three new classes. Furthermore, we give applications of our characterizations to some forbidden subgraph problems.

preprint2015arXiv

Dominating cycles and forbidden pairs containing a path of order 5

A cycle is a graph is dominating if every edge of the graph is incident with a vertex of the cycle. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every $2$ -connected $\{P_{5}, K_{4}^{-}\}$ -free graph contains a longest cycle which is a dominating cycle. (ii) Every $2$ -connected $\{P_{5}, W^{*}\}$ -free graph contains a longest cycle which is a dominating cycle. Here $P_{5}$ is the path of order $5$ , $K_{4}^{-}$ is the graph obtained from the complete graph of order $4$ by removing one edge, and $W^{*}$ is a graph obtained from two triangles and an edge by identifying one vertex in each.

preprint2015arXiv

Forbidden pairs and the existence of a dominating cycle

A cycle in a graph is called dominating if every edge of the graph is incident with a vertex of the cycle. In this paper, we investigate forbidden pairs guaranteeing the existence of a dominating cycle in 2-connected graphs.

preprint2015arXiv

Partitioning a graph into highly connected subgraphs

Given $k\ge 1$ , a $k$ -proper partition of a graph $G$ is a partition ${\mathcal P}$ of $V(G)$ such that each part $P$ of ${\mathcal P}$ induces a $k$ -connected subgraph of $G$ . We prove that if $G$ is a graph of order $n$ such that $δ(G)\ge \sqrt{n}$ , then $G$ has a $2$ -proper partition with at most $n/δ(G)$ parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that If $G$ is a graph of order $n$ with minimum degree $δ(G)\ge\sqrt{c(k-1)n}$ , where $c=\frac{2123}{180}$ , then $G$ has a $k$ -proper partition into at most $\frac{cn}{δ(G)}$ parts. This improves a result of Ferrara, Magnant and Wenger [Conditions for Families of Disjoint $k$ -connected Subgraphs in a Graph, Discrete Math. 313 (2013), 760--764] and both the degree condition and the number of parts are best possible up to the constant $c$ .

preprint2015arXiv

Path-factors involving paths of order seven and nine

In this paper, we show the following two theorems (here $c_{i}(G-X)$ is the number of components $C$ of $G-X$ with $|V(C)|=i$ ): (i)~If a graph $G$ satisfies $c_{1}(G-X)+\frac{1}{3}c_{3}(G-X)+\frac{1}{3}c_{5}(G-X)\leq \frac{2}{3}|X|$ for all $X\subseteq V(G)$ , then $G$ has a $\{P_{2},P_{7}\}$ -factor. (ii)~If a graph $G$ satisfies $c_{1}(G-X)+c_{3}(G-X)+\frac{2}{3}c_{5}(G-X)+\frac{1}{3}c_{7}(G-X)\leq \frac{2}{3}|X|$ for all $X\subseteq V(G)$ , then $G$ has a $\{P_{2},P_{9}\}$ -factor.

preprint2015arXiv

The existence of a path-factor without small odd paths

In this paper, we show that if a graph $G$ satisfies $c_{1}(G-X)+\frac{2}{3}c_{3}(G-X)\leq \frac{4}{3}|X|+\frac{1}{3}$ for all $X\subseteq V(G)$ , then $G$ has a $\{P_{2},P_{5}\}$ -factor, where $c_{i}(G-X)$ is the number of components $C$ of $G-X$ with $|V(C)|=i$ .

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.

Michitaka Furuya

Research overview

Is this your work?

10 publications

A continuous generalization of domination-like invariants

The uniqueness of covers for widely generalized line graphs

A characterization of domination weak bicritical graphs with large diameter

A New Approach Towards a Conjecture on Intersecting Three Longest Paths

Difference of forbidden pairs containing a claw

Dominating cycles and forbidden pairs containing a path of order 5

Forbidden pairs and the existence of a dominating cycle

Partitioning a graph into highly connected subgraphs

Path-factors involving paths of order seven and nine

The existence of a path-factor without small odd paths

See the researcher in context

Building this map preview