Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

Lower bounds on the signed domination numbers of directed graphs

A numerical invariant of directed graphs concerning domination which is named signed domination number γ_S is studied in this paper. We present some sharp lower bounds for γ_S in terms of the order, the maximum degree and the chromatic number of a directed graph.     

Lower bounds on several versions of signed domination number

Three numerical invariants of graphs concerning domination, which are named the signed domination number γ_s, the k-subdomination number γ_ks and the signed total domination number γ_st, are studied in this paper. For any graph, some lower bounds on γ_s, γ_ks and γ_st are presented, some of which generalize several known lower bounds on γ_s, γ_ks and γ_st, while others are considered as new. It is also shown that these bounds are sharp.     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.     

Lower bounds on the maximum number of non-crossing acyclic graphs

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of $N$ points has $\Omega \left(12.52^N\right)$ non-crossing spanning trees and $\Omega \left(13.61^N\right)$ non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of $N$ points in general position given by Dumitrescu, Schulz, Sheffer and Tóth (2013). Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of $O\left(22.12^N\right)$ for the number of non-crossing spanning trees of the double chain is also obtained.     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.     

A note on the signed edge domination number in graphs

Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑_e^′N[e]f(e^′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs G_m,k with .     

Lower bounds for transition probabilities on graphs

The paper presents two results. The first one provides separate conditions for the upper and lower estimates of the distribution of the time of exit from balls of a random walk on a weighted graph. The main result of the paper is that the lower estimate follows from the elliptic Harnack inequality. The second result is an off-diagonal lower bound for the transition probability of the random walk.     

Lower bounds for combinatorial problems on graphs

Nontrivial lower bounds are given for the computation time of various combinatorial problems on graphs under a linear or algebraic decision tree model. An $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is obtained for a “travelling salesman problem” on a weighted complete graph of n vertices. Moreover it is shown that the same bound is valid for the “subgraph detection problem” with respect to property P if P is hereditary and determined by components. Thus an $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is established in a unified way for a rather large class of problems.     

Flow number and circular flow number of signed cubic graphs

Let $\mathrm{\Phi }(G,\sigma )$ and ${\mathrm{\Phi }}_c(G,\sigma )$ denote the flow number and the circular flow number of a flow-admissible signed graph $(G,\sigma )$, respectively. It is known that $\mathrm{\Phi }(G)=?{\mathrm{\Phi }}_c(G)?$ for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that $\mathrm{\Phi }(G,\sigma )?{\mathrm{\Phi }}_c(G,\sigma )<1$ holds also for every flow-admissible signed graph $(G,\sigma )$. This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that $\mathrm{\Phi }(G,\sigma )=3$ if and only if ${\mathrm{\Phi }}_c(G,\sigma )=3$ and if $\mathrm{\Phi }(G,\sigma )\in \{4,5\}$, then $4\le {\mathrm{\Phi }}_c(G,\sigma )\le \mathrm{\Phi }(G,\sigma )$. We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area.     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Some bounds on the injective chromatic number of graphs

We give some bounds on the injective chromatic number.     

On signed majority total domination in graphs

We initiate the study of signed majority total domination in graphs. Let G = (V, E) be a simple graph. For any real valued function f: V and S V, let . A signed majority total dominating function is a function f: V {–1, 1} such that f(N(v)) 1 for at least a half of the vertices v V. The signed majority total domination number of a graph G is = min{f(V): f is a signed majority total dominating function on G}. We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of .This research was supported by National Natural Science Foundation of China.