Results 21 to 30 of about 668 (63)
Open k-monopolies in graphs: complexity and related concepts [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis ...
Dorota Kuziak +2 more
doaj +1 more source
A version of Herbert A. Simon's model with slowly fading memory and its connections to branching processes [PDF]
, 2019 Construct recursively a long string of words w1. .. wn, such that at each step k, w k+1 is a new word with a fixed probability p $\in$ (0, 1), and repeats some preceding word with complementary probability 1 -- p.
Bertoin, Jean
core +1 more source
On partial sorting in restricted rounds
Acta Universitatis Sapientiae: Informatica, 2017 Let n and k be integers such that n ≥ 2 and 1 ≤ k ≤n. In this paper, we consider the problem of finding an ordered list of the k best players out of n participants by organizing a tournament of rounds of pairwise matches (comparisons).
Iványi Antal, Fogarasi Norbert
doaj +1 more source
Further results on Parity Combination Cordial Labeling
Journal of the Egyptian Mathematical Society, 2020 Let G be a (p, q)-graph. Let f be an injective mapping from V(G) to {1, 2, …, p}. For each edge xy, assign the label x y $$ \left(\genfrac{}{}{0pt}{}{x}{y}\right) $$ or y x $$ \left(\genfrac{}{}{0pt}{}{y}{x}\right) $$ according as x > y or y > x.
Mohamed Seoud, Mohamed Aboshady
doaj +1 more source
J-coloring of graph operations
Acta Universitatis Sapientiae: Informatica, 2019 A vertex v of a given graph is said to be in a rainbow neighbourhood of G if every color class of G consists of at least one vertex from the closed neighbourhood N[v].
Naduvath Sudev, Kok Johan
doaj +1 more source
Bounds for the smallest $k$-chromatic graphs of given girth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$.
Geoffrey Exoo, Jan Goedgebeur
doaj +1 more source
Soft covering based rough graphs and corresponding decision making
Open Mathematics, 2019 Soft set theory and rough set theory are two new tools to discuss uncertainty. Graph theory is a nice way to depict certain information. Particularly soft graphs serve the purpose beautifully.
Park Choonkil +5 more
doaj +1 more source
A Linear Kernel for Planar Total Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when ...
Valentin Garnero, Ignasi Sau
doaj +1 more source
Evasive Properties of Sparse Graphs and Some Linear Equations in Primes
, 2013 We give an unconditional version of a conditional, on the Extended Riemann Hypothesis, result of L. Babai, A. Banerjee, R. Kulkarni and V. Naik (2010) on the evasiveness of sparse graphs.Comment: This version corrects a mistake made in the previous ...
Shparlinski, Igor
core +1 more source
Discussiones Mathematicae Graph Theory, 2017 We characterize the class L32$L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs.
Metelsky Yury +2 more
doaj +1 more source