Results 31 to 40 of about 70 (68)
The Second Neighbourhood for Bipartite Tournaments
Discussiones Mathematicae Graph Theory, 2019 Let T (X ∪ Y, A) be a bipartite tournament with partite sets X, Y and arc set A. For any vertex x ∈ X ∪Y, the second out-neighbourhood N++(x) of x is the set of all vertices with distance 2 from x.
Li Ruijuan, Sheng Bin
doaj +1 more source
The Subset-Strong Product of Graphs
Annales Mathematicae SilesianaeIn this paper, we introduce the subset-strong product of graphs and give a method for calculating the adjacency spectrum of this product. In addition, exact expressions for the first and second Zagreb indices of the subset-strong products of two graphs ...
Eliasi Mehdi
doaj +1 more source
Brouwer's conjecture for the sum of the k largest Laplacian eigenvalues of some graphs
Open MathematicsLet GG be a graph with n(G)n\left(G) vertices and e(G)e\left(G) edges, and Sk(G){S}_{k}\left(G) be the sum of the kk largest Laplacian eigenvalues of GG. Brouwer conjectured that Sk(G)≤e(G)+k+12{S}_{k}\left(G)\le e\left(G)+\left(\phantom{\rule[-0.75em]{}{
Wang Ke +3 more
doaj +1 more source
On the existence of tripartite graphs and n-partite graphs
Open MathematicsA sequence α\alpha of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph GG, and such a graph GG is called a realization of α\alpha .
Guo Jiyun +4 more
doaj +1 more source
Rejection sampling of bipartite graphs with given degree sequence
Acta Universitatis Sapientiae: Mathematica, 2018 Let A = (a1, a2, ..., an) be a degree sequence of a simple bipartite graph. We present an algorithm that takes A as input, and outputs a simple bipartite realization of A, without stalling.
Kayibi Koko K. +3 more
doaj +1 more source
Irreversible 2-conversion set in graphs of bounded degree [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$
Jan Kynčl +2 more
doaj +1 more source
A Constructive Extension of the Characterization on Potentially Ks,t-Bigraphic Pairs
Discussiones Mathematicae Graph Theory, 2017 Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2
Guo Ji-Yun, Yin Jian-Hua
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2018 A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum
Górska Joanna +4 more
doaj +1 more source
The Bipartite-Splittance of a Bipartite Graph
Discussiones Mathematicae Graph Theory, 2019 A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in ...
Yin Jian-Hua, Guan Jing-Xin
doaj +1 more source
New Formulae for the Decycling Number of Graphs
Discussiones Mathematicae Graph Theory, 2019 A set S of vertices of a graph G is called a decycling set if G−S is acyclic. The minimum order of a decycling set is called the decycling number of G, and denoted by ∇(G). Our results include: (a) For any graph G,, where T is taken over all the spanning
Yang Chao, Ren Han
doaj +1 more source