A lower bound for the distance k-domination number of trees

A subset D of vertices of a graph G = (V, E) is a distance k-dominating set for G if the distance between every vertex of V ? D and D is at most k. The minimum size of a distance k-dominating set of G is called the distance k-domination number γ_k(G) of G. In this paper we prove that (2k + 1)γ_k(T) ≥ ¦V¦ + 2k ? kn₁ for each tree T = (V, E) with n₁ leafs, and we characterize the class of trees that satisfy the equality (2k + 1)γ_k(T) = ¦V¦ + 2k ? kn₁. Our results generalize those of Lemanska [4] for k = 1 and of Cyman, Lemanska and Raczek [1] for k = 2.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

Graph Decompositions Satisfying Extremal Degree Constraints

We show that the vertex set of any graph G with p?2 vertices can be partitioned into non-empty sets V₁, V₂, such that the maximum degree of the induced subgraph 〈V_i〉 does not exceed where pⁱ = |Vⁱ|, for i=1, 2. Furthermore, the structure of the induced subgraphs is investigated in the extreme case.     

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥_n-factor if its each component admits at least n vertices. A graph G is called P≥_n-factor covered if G admits a P≥_n-factor containing e for any e ∈ E(G), which is defined by[Discrete Mathematics, 309, 2067–2076(2009)]. We first define the concept of a(P≥_n, k)-factor-critical covered graph, namely, a graph G is called(P≥_n, k)-factor-critical covered if G-D is P≥_n-factor covered for any D ? V(G) with |D| = k. In this paper, we verify that(i) a graph G with κ(G) ≥ k + 1 is(P≥2, k)-factor-critical covered if bind(G) 2+k/3;(ii) a graph G with |V(G)| ≥ k + 3 and κ(G) ≥ k + 1 is(P≥3, k)-factor-critical covered if bind(G) ≥4+k/3.     

Star partitions of graphs

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V₁,…,V_m) of V (G) such that each V_i induces one of stars K_1,1,…,K_1,n, and (ii) for every subset S of V(G), G\ S has at most n|S| components with the property that each of their blocks is an odd order complete graph. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 185–190, 1997     

Balanced judicious bipartitions of graphs

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V₁, V₂ such that for each i, G has at most |E(G)|/3 edges with both ends in V_i. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G(i.e., when Δ(G)=δ(G)). We prove this conjecture for graphs G with \begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}; hence, it holds for graphs ]ensuremathG with \begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean

Path chromatic numbers of graphs

Let the finite, simple, undirected graph G = (V(G), E(G)) be vertex-colored. Denote the distinct colors by 1,2,…,c. Let V_i be the set of all vertices colored j and let <V_i be the subgraph of G induced by V_i. The k-path chromatic number of G, denoted by χ(G; P_k), is the least number c of distinct colors with which V(G) can be colored such that each connected component of V_i is a path of order at most k, 1 ? i ? c. We obtain upper bounds for χ(G; P_k) and χ(G; P_∞) for regular, planar, and outerplanar graphs.     

An asymptotic of the negative discrete spectrum of the Schrödinger operator

The Schrödinger operator Hu = -Δu + V(x)u, where V(x) → 0 as ¦x¦ → ∞, is considered in L₂(R^m) for m?3. The asymptotic formula $$N(\lambda ,V) \sim \Upsilon _m \int {(\lambda - V(x))_ + ^{{m \mathord{\left/ {\vphantom {m {2_{dx} }}} \right. \kern-\nulldelimiterspace} {2_{dx} }}} ,} \lambda \to ---0,$$ is established for the number N(λ, V) of the characteristic values of the operator H which are less than λ. It is assumed about the potential V that V = V_o + V₁; V_o < 0, ¦V_o =o (¦V_o¦^3/2) as ¦x¦ → ∞; σ (t/2, V_o) ?cσ (t. V_o) and V₁∈L_m/2,loc, σ(t, V₁) =o (σ (t, V_o)), where σ (t,f)= mes {x:¦f (x) ¦ > t).     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

Judicious partitions of weighted hypergraphs

Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott: Does there exist a bipartition such that each class meets edges of total weight at least (w_1-α)/2+(2w_2)/3? We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes.In particular, it is shown that any graph G with m edges has a partition V_1,..., V_k such that each vertex set meets at least(1-(1-1/k)~2)m + o(m) edges, which answers a related question of Bollobás and Scott.     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

整数距离图G(D_(m,k,2))的点荫度

图G的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目,其中任一子集的点导出子图都是森林.整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m2k≥2,令D_(m,k,2)=[1,m]\{k,2k}.该文得出了整数距离图G(D_(m,k,2))的点荫度的几个上、下界;进而,对于m≥4,有va(G(D_(m,1,2)))=[(m+4)/5];对于m=10q+j,j=0,1,2,3,5,6,有va(G(D_(m,2,2)))=[(m+1)/5]+1.     

A NOTE ON GRAPHS WHOSE DESTRUCTIONS YIELD COMPLETE SUBGRAPHS

Abstract

A connected graph G of order p =|V| and sise q =| E | is said to be (a_i, b_i)-destructible (with respect to E_i and V_i say) if a_i,b_i are integral factors of p and an a_i-set of edges E_i exists whose removal from G results in exactly b_i components isomorphic to K_i i.e. whose removal from G isolates the vertices in a b_i-set V_i. The operation of removing E_i and V_i from G results in either Ø or a subgraph H of G and is called an (a_i , b_i)-destruction of G. In this paper we show that the only graphs whose every (a_i,b_i)- destruction results in a complete subgraph are K (1,2) and K₄—e, where e ε K₄.     

A function of direction associated with n congruences of an orthogonal ennuple in a Riemannian hypersurface

In a hypersurface V_n belonging to a Riemannian space V_n+1 we choose n congruences of an orthogonal ennuple of unit vectors of contravariant components λ _h¦ ⁱ (h=1,2,...,n) and denote, by ω_kk the normal curvature of the hypersurface in the direction of the unit vector of components λ _k¦ ⁱ . In the present paper, we have shown that the expression $$\frac{\partial }{{\partial s_k }}\omega _{kk} - 2\mathop \Sigma \limits_{h = 1}^n \omega _{kh} \gamma _{hkk}$$ is a function of direction, where the symbol ?/?s_k indicates the differentiation in the direction of the vector of components λ _k¦ ⁱ and that ω_kh (h≠k) and γ_?hk (?,h,k=1,2,...,n) are, respectively, the invariants of the geodesic torsion of the curve of the congruence with unit tangent vector of components λ _k¦ ⁱ and Ricci's coefficients of rotation of the orthogonal ennuple.