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.
Bell and Stirling numbers for graphs.
Bi-Induced Subgraphs and Stability Number
Bipartite diametrical graphs of diameter 4 and extreme orders.
Bipartition Polynomials, the Ising Model, and Domination in Graphs
This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants....
Boundary domination in graphs
Bounds concerning the alliance number
P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number , strong defensive alliance number , and global defensive alliance number . In this paper, we consider relationships between these parameters and the domination number . For any positive integers...
Bounds on global secure sets in cactus trees
Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global...
Bounds on Laplacian eigenvalues related to total and signed domination of graphs
A total dominating set in a graph is a subset of such that each vertex of is adjacent to at least one vertex of . The total domination number of is the minimum cardinality of a total dominating set. A function is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of is the minimum weight of an SDF on . In this paper...
Bounds on Roman domination numbers of graphs