BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A P3-decomposition of a directed graph D is a partition of the arcs of D into directed paths of length 2. In this paper, we give a characterization for a tournament and a bipartite digraph admitting a P3-decomposition. This solves a problem posed by Diwan (P3-decomposition of directed graphs, Discrete Appl. Math., http:// dx.doi.org/10.1016/j.dam.2016.01.039.).
An edge subset S of a connected graph G is called an anti-Kekulé set if G−S is connected and has no perfect matching. We can see that a connected graph G has no anti-Kekulé set if and only if each spanning tree of G has a perfect matching. In this paper, by applying Tutte's 1-factor theorem and structure of minimally 2-connected graphs, we characterize all graphs whose each spanning tree has a perfect matching In addition, we show that if G is a connected graph of order 2n for a positive integer n≥4 and size m whose each spanning tree has a perfect matching, then m≤2(n+1)n, with equality if and only if G≅Kn∘K1.
The Catalan-Larcombe-French sequence {Pn}n≥0 arises in a series expansion of the complete elliptic integral of the first kind. It has been proved that the sequence is log-balanced. In the paper, by exploring a criterion due to Chen and Xia for testing 2-log-convexity of a sequence satisfying three-term recurrence relation, we prove that the new sequence {Pn2−Pn−1Pn+1}n≥1 are strictly log-convex and hence the Catalan-Larcombe-French sequence is strictly 2-log-convex.
A coloring of a graph G=(V,E) is a partition {V1,V2,…,Vk} of V into independent sets or color classes. A vertex v∈Vi is a Grundy vertex if it is adjacent to at least one vertex in each color class Vj for every j<i. A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number Γ(G) of a graph G is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a {P4,C4}-free graph by supporting a conjecture of Zaker, which says that Γ(G)≥δ(G)+1 for any C4-free graph G.
Amos et al. (Discrete Appl. Math. 181 (2015) 1-10) introduced the notion of the k-forcing number of graph for a positive integer k as the generalization of the zero forcing number of a graph. The k-forcing number of a simple graph G, denoted by Fk(G), is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most k non-colored neighbors, then each of its non-colored neighbors become colored. Particulary, F1(G) is a widely studied invariant with close connection to the maximum nullity of a graph, under the name of the zero forcing number, denoted by Z(G). Among other things, the authors proved that for a connected graph G of order n with Δ=Δ(G)≥2, Z(G)≤Δ−1(Δ−2)n+2, and this inequality is sharp. Moreover, they conjectured that Z(G)=Δ−1(Δ−2)n+2 if and only if G=Cn, G=KΔ+1 or G=KΔ,Δ. In this note, we show the above conjecture is true.
Let G be a connected graph of order n with diameter d. Remoteness ρ of G is the maximum average distance from a vertex to all others and ∂1≥⋯≥∂n are the distance eigenvalues of G. In \cite{AH}, Aouchiche and Hansen conjectured that ρ+∂3>0 when d≥3 and ρ+∂⌊87d⌋>0. In this paper, we confirm these two conjectures. Furthermore, we give lower bounds on ∂n+ρ and ∂1−ρ when G≆Kn and the extremal graphs are characterized.
A subset S⊆V in a graph G=(V,E) is a total [1,2]-set if, for every vertex v∈V, 1≤∣N(v)∩S∣≤2. The minimum cardinality of a total [1,2]-set of G is called the total [1,2]-domination number, denoted by γt[1,2](G). We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1,2]-set and for a graph with the same total [1,2]-domination number, [1,2]-domination number and domination number.
Dvořák \emph{et al.} introduced a variant of the Randić index of a graph G, denoted by R′(G), where R′(G)=∑uv∈E(G)max{d(u),d(v)}1, and d(u) denotes the degree of a vertex u in G. The coloring number col(G) of a graph G is the smallest number k for which there exists a linear ordering of the vertices of G such that each vertex is preceded by fewer than k of its neighbors. It is well-known that χ(G)≤col(G) for any graph G, where χ(G) denotes the chromatic number of G. In this note, we show that for any graph G without isolated vertices, col(G)≤2R′(G), with equality if and only if G is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph.
We characterize, by easily verifiable properties, abstract ternary relations isomorphic to the causal betweenness introduced by Hans Reichenbach.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.