Acyclic numbers of graphs.
Algorithmic aspects of total-subdomination in graphs
Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination...
Almost all trees have an even number of independent sets.
An approximation algorithm for the total covering problem
We introduce a 2-factor approximation algorithm for the minimum total covering number problem.
An inequality related to Vizing's conjecture.
An optimal strongly identifying code in the infinite triangular grid.
An upper bound for domination number of 5-regular graphs
Let be a simple graph. A subset is a dominating set of , if for any vertex , there exists a vertex such that . The domination number, denoted by , is the minimum cardinality of a dominating set. In this paper we will prove that if is a 5-regular graph, then .
Analogues of cliques for oriented coloring
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
Approximation algorithms for some graph partitioning problems.
Approximations of weighted independent set and hereditary subset problems.
Arithmetically maximal independent sets in infinite graphs
Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.