Results 11 to 20 of about 703 (75)
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
From graphs to tensegrity structures: Geometric and symbolic approaches [PDF]
, 2004 A form-finding problem for tensegrity structures is studied; given an abstract graph,we show an algorithm to provide a necessary condition for it to be the underlying graphof a tensegrity in R d (typically d = 2,3) with vertices in general position ...
Miguel de Guzm'an, David Orden
semanticscholar +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 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
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 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
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
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