Source author record

Shinya Fujita

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

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

New classification of graphs in view of the domination number of central graphs

For a graph $G$ , the central graph $C(G)$ is the graph constructed from $G$ by subdividing each edge of $G$ with one vertex and also by adding an edge to every pair of non-adjacent vertices in $G$ . Also for a graph $G$ , let $γ(G)$ and $τ(G)$ be the domination number of $G$ and the minimum cardinarity of a vertex cover of $G$ , respectively. In this paper, we give a new classification of graphs concerning the domination number of central graphs and minimum vertex covers of graphs. Namely, we show that any graph $G$ with at least three vertices can be classified into one of the two classes of graphs with $γ(C(G))=τ(G)$ and $γ(C(G))=τ(G)+1$ , respectively, together with some special properties concerning a vertex cover of $G$ . We also give some new results on the domination number of central graphs.

preprint2021arXiv

On properly ordered coloring of vertices in a vertex-weighted graph

We introduce the notion of a properly ordered coloring (POC) of a weighted graph, that generalizes the notion of vertex coloring of a graph. Under a POC, if $xy$ is an edge, then the larger weighted vertex receives a larger color; in the case of equal weights of $x$ and $y$ , their colors must be different. In this paper, we shall initiate the study of this special coloring in graphs. For a graph $G$ , we introduce the function $f(G)$ which gives the maximum number of colors required by a POC over all weightings of $G$ . We show that $f(G)=\ell(G)$ , where $\ell(G)$ is the number of vertices of a longest path in $G$ . Another function we introduce is $χ_{POC}(G;t)$ giving the minimum number of colors required over all weightings of $G$ using $t$ distinct weights. We show that the ratio of $χ_{POC}(G;t)-1$ to $χ(G)-1$ can be bounded by $t$ for any graph $G$ ; in fact, the result is shown by determining $χ_{POC}(G;t)$ when $G$ is a complete multipartite graph. We also determine the minimum number of colors to give a POC on a vertex-weighted graph in terms of the number of vertices of a longest directed path in an orientation of the underlying graph. This extends the so called Gallai-Hasse-Roy-Vitaver theorem, a classical result concerning the relationship between the chromatic number of a graph $G$ and the number of vertices of a longest directed path in an orientation of $G$ .

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)$ .

preprint2020arXiv

The optimal proper connection number of a graph with given independence number

An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${\mathrm{pc}_{\mathrm{opt}}}(G)$ for a monochromatic connected graph $G$ , to make a connected graph properly connected efficiently. More precisely, ${\mathrm{pc}_{\mathrm{opt}}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${\mathrm{pc}_{\mathrm{opt}}}(G)$ has an upper bound in terms of the independence number $α(G)$ . Namely, we prove that for a connected graph $G$ , ${\mathrm{pc}_{\mathrm{opt}}}(G)\le \frac{5α(G)-1}{2}$ . Moreoevr, for the case $α(G)\leq 3$ , we improve the upper bound to $4$ , which is tight.

preprint2020arXiv

The size of graphs with restricted rainbow $2$ -connection number

Let $k$ be a positive integer, and $G$ be a $k$ -connected graph. An edge-coloured path is \emph{rainbow} if all of its edges have distinct colours. The \emph{rainbow $k$ -connection number} of $G$ , denoted by $rc_k(G)$ , is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $rc_k(G)$ was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$ -connected graph $G$ on $n$ vertices with $rc_k(G)\le r$ . Let $s_k(n,r)$ denote the maximum number of edges in a $k$ -connected graph $G$ on $n$ vertices with $rc_k(G)\ge r$ . The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$ . We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))n\log_2 n$ , and $t_2(n,r)$ is linear in $n$ for $r\ge 3$ . We also provide some remarks about the function $s_2(n,r)$ .

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

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$ .

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.

Shinya Fujita

Research overview

Is this your work?

7 publications

New classification of graphs in view of the domination number of central graphs

On properly ordered coloring of vertices in a vertex-weighted graph

Stable structure on safe set problems in vertex-weighted graphs

The optimal proper connection number of a graph with given independence number

The size of graphs with restricted rainbow $2$ -connection number

A New Approach Towards a Conjecture on Intersecting Three Longest Paths

Partitioning a graph into highly connected subgraphs

See the researcher in context

Building this map preview

Shinya Fujita

Research overview

Is this your work?

7 publications

New classification of graphs in view of the domination number of central graphs

On properly ordered coloring of vertices in a vertex-weighted graph

Stable structure on safe set problems in vertex-weighted graphs

The optimal proper connection number of a graph with given independence number

The size of graphs with restricted rainbow 222-connection number

A New Approach Towards a Conjecture on Intersecting Three Longest Paths

Partitioning a graph into highly connected subgraphs

See the researcher in context

Building this map preview

The size of graphs with restricted rainbow $2$ -connection number