Results 21 to 30 of about 104 (103)
On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
Discussiones Mathematicae Graph Theory, 2018 In the paper, we show that the incidence chromatic number χi of a complete k-partite graph is at most Δ + 2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to Δ + 1 if and only if the smallest part has only one vertex ...
Janczewski Robert +2 more
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
Classification of Filiform Lie Algebras up to dimension 7 Over Finite Fields
Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica, 2016 This paper tries to develop a recent research which consists in using Discrete Mathematics as a tool in the study of the problem of the classification of Lie algebras in general, dealing in this case with filiform Lie algebras up to dimension 7 over ...
Falcón Óscar J. +4 more
doaj +1 more source
Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3] [PDF]
Discrete Mathematics & Theoretical Computer ScienceIn this corrigendum, we give a counterexample to Theorem 5.2 in "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]. We also present a polynomial-time algorithm for computing the monophonic rank of a starlike
Mitre C. Dourado +2 more
doaj +1 more source
Constructing Regular Self-complementary Uniform Hypergraphs [PDF]
, 2011 AMS Subject Classication Codes: 05C65, 05B05 05E20, 05C85.In this paper, we examine the possible orders of t-subset-regular self-complementary k-uniform hypergraphs, which form examples of large sets of two isomorphic t-designs.
Gosselin, Shonda, Shonda Gosselin
core +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
Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts.
Luerbio Faria +3 more
doaj +1 more source
Hardness Results and Spectral Techniques for Combinatorial Problems on Circulant Graphs [PDF]
, 1998 We show that computing (and even approximating) MAXIMUM CLIQUE and MINIMUM GRAPH COLORING for circulant graphs is essentially as hard as in the general case.
Ivan Gerace +8 more
core +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
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