The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

New upper bounds for the chromatic number of a graph*

We show that for any graph G, the chromatic number χ(G) ≤ Δ₂(G) + 1, where Δ₂(G) is the largest degree that a vertex ν can have subject to the condition that ν is adjacent to a vertex whose degree is at least as big as its own. Moreover, we show that the upper bound is best possible in the the following sense: If Δ₂(G) ≥ 3, then to determine whether χ(G) ≤ Δ₂(G) is an NP‐complete problem. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 117–120, 2001     

Circular mixed hypergraphs II:The upper chromatic number

A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C, D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:X→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. A mixed hypergraph H is called circular if there exists a host cycle on the vertex set X such that every edge (C- or D-) induces a connected subgraph of this cycle.We suggest a general procedure for coloring circular mixed hypergraphs and prove that if H is a reduced colorable circular mixed hypergraph with n vertices, upper chromatic number and sieve number s, then

     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

On strongly jump traceable reals

In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is -complete.     

An upper bound for domination number of 5-regular graphs

Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n.     

The upper bound of the number of cycles in a 2‐factor of a line graph

Let G be a simple graph with order n and minimum degree at least two. In this paper, we prove that if every odd branch‐bond in G has an edge‐branch, then its line graph has a 2‐factor with at most components. For a simple graph with minimum degree at least three also, the same conclusion holds. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 72–82, 2007     

On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γ_R(G) is called a γ_R(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V₀,V₁,V₂) of V, where V_i={v∈V∣f(v)=i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V₀|,|V₁|,|V₂| for a γ_R-function f=(V₀,V₁,V₂) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γ_R-function f=(V₀,V₁,V₂) of a connected graph G of order n≥3, , and .     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

On the doubly connected domination number of a graph

For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.     

The competition number of a graph whose holes do not overlap much

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between u and v if and only if there exists a vertex x in D such that (u,x) and (v,x) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices.A hole of a graph is an induced cycle of length at least four. Kim (2005) [8] conjectured that the competition number of a graph with h holes is at most h+1. Recently, Li and Chang (2009) [11] showed that the conjecture is true when the holes are independent. In this paper, we show that the conjecture is true though the holes are not independent but mutually edge-disjoint.     

On a conjecture concerning the orientation number of a graph

For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number of G is defined by . Let G(p,q;m) denote the family of simple graphs obtained from the disjoint union of two complete graphs K_p and K_q by adding m edges linking them in an arbitrary manner. The study of the orientation numbers of graphs in G(p,q;m) was introduced by Koh and Ng [K.M. Koh, K.L. Ng, The orientation number of two complete graphs with linkages, Discrete Math. 295 (2005) 91-106]. Define and . In this paper we prove a conjecture on α proposed by K.M. Koh and K.L. Ng in the above mentioned paper, for q≥p+4.     

About the upper chromatic number of a co-hypergraph

A mixed hypergraph consists of two families of subsets: the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is termed the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored. The necessary and sufficient conditions for determining the upper chromatic numbers, of a co-hypergraph are provided. And the bounds of the number of co-edges of some uniform co-hypergraphs with certain upper chromatic numbers are given.     

Research problem: The completion number of a graph

Motivated by the remarkable connection between graph theory and matrix analysis, we associate to each graph a so-called completion number that might encode some aspects of this interplay. We show that this number is not trivial, and we ask for a graph-theoretic characterization of those graphs with a given completion number.