Results 11 to 20 of about 668 (63)
Degree tolerant coloring of graph
Acta Universitatis Sapientiae: Informatica, 2020 This paper initiates a study on a new coloring regime which sets conditions in respect of the degrees deg(v) and deg(u) where, v, u ∈ V(G) and vu ∈ E(G). This new coloring regime is called, ”degree tolerant coloring”. The degree tolerant chromatic number
Kok Johan
doaj +1 more source
On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A mixed dominating set for a graph $G = (V,E)$ is a set $S\subseteq V \cup E$ such that every element $x \in (V \cup E) \backslash S$ is either adjacent or incident to an element of $S$. The mixed domination number of a graph $G$, denoted by $\gamma_m(G)$
M. Rajaati +3 more
doaj +1 more source
On rank-width of even-hole-free graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C.
Isolde Adler +5 more
doaj +1 more source
A Note on Quasi-Triangulated Graphs [PDF]
, 2006 A graph is quasi-triangulated if each of its induced subgraphs has a vertex which is either simplicial (its neighbors form a clique) or cosimplicial (its nonneighbors form an independent set).
Gorgos, Ion +2 more
core +2 more sources
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
Sinks in Acyclic Orientations of Graphs [PDF]
, 1999 Greene and Zaslavsky proved that the number of acyclic orientations of a graph with a unique sink is, up to sign, the linear coefficient of the chromatic polynomial.
Gebhard, David D., Sagan, Bruce E.
core +3 more sources
A measure of graph vulnerability: scattering number
International Journal of Mathematics and Mathematical Sciences, Volume 30, Issue 1, Page 1-8, 2002., 2002 The scattering number of a graph G, denoted sc(G), is defined by sc(G) = max{c(G − S) − |S| : S⫅V(G) and c(G − S) ≠ 1} where c(G − S) denotes the number of components in G − S. It is one measure of graph vulnerability. In this paper, general results on the scattering number of a graph are considered.
Alpay Kirlangiç
wiley +1 more source
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
Finding Hamilton cycles in random intersection graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a
Katarzyna Rybarczyk
doaj +1 more source
A Decomposition Theorem for Maximum Weight Bipartite Matchings [PDF]
, 1999 Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of G. Let k(x,y) be log(x)/log(x^2/y). We present a new decomposition theorem
Kao, Ming-Yang +3 more
core +3 more sources