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 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.     

A circular embedding of a graph in Euclidean 3-space

A spatial embedding of a graph G is an embedding of G into the 3-dimensional Euclidean space . J.H. Conway and C.McA. Gordon proved that every spatial embedding of the complete graph on 7 vertices contains a nontrivial knot. A linear spatial embedding of a graph is an embedding which maps each edge to a single straight line segment. In this paper, we construct a linear spatial embedding of the complete graph on 2n−1 (or 2n) vertices which contains the torus knot T(2n−5,2) (n4). A circular spatial embedding of a graph is an embedding which maps each edge to a round arc. We define the circular number of a knot as the minimal number of round arcs in among such embeddings of the knot. We show that a knot has circular number 3 if and only if the knot is a trefoil knot, and the figure-eight knot has circular number 4.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

关于树T的γ/γc的界

控制γ和连通控制数γc是图的两个重要的控制参数，本文通过对树中的点进行恰当分类，给出了树中的γ/γc值的最好界，为刻画单圈图和双圈图中γ/γc值的界打下良好的基础。     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Inequalities of Nordhaus-Gaddum type for doubly connected domination number

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγ_cc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound.     

任意基数集上的拟阵的圈及连通性

通过研究任意基数集上的拟阵圈的性质,继而得出当此拟阵连通时,它可由含任一给定元素的圈集唯一确定的结论.     

On the bilinear and cubic forms of some symplectic connected sums

Let ( M1 , M2 , N ) be three symplectic manifolds and suppose that we can do the symplectic connected sum of M1 and M2 along their submanifold N to obtain M1#NM2 . In this paper, we consider the bilinear and cubic forms of H* (M1#NM2 , Z) when dim M1#NM2 = 4, 6. Under some conditions, we get some relations of the bilinear and the cubic forms between M1#NM2 and M1■M2 .     

Levels Sets Infimal Convolution and Level Addition

A sufficient criterion is established for the infimal convolution of two functions having connected level sets to share the same property without being exact. As a consequence, the infimal convolution of quasiconvex functions on a real line is quasiconvex. However, this is not true on a space of higher dimension, which is illustrated by an example in R ². Furthermore, connectedness of level sets and local-global minimum properties of functions are analyzed under level addition. Continuity properties of level set maps are also studied in relation with local-global minimum properties.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Coloring the Cartesian sum of graphs

For graphs G and H, let G⊕H denote their Cartesian sum. We investigate the chromatic number and the circular chromatic number for G⊕H. It has been proved that for any graphs G and H, . It has been conjectured that for any graphs G and H, . We confirm this conjecture for graphs G and H with special values of χ_c(G) and χ_c(H). These results improve previously known bounds on the corresponding coloring parameters for the Cartesian sum of graphs.     

一个素变数丢番图不等式

本文证明了如果1相似文献   

一个二元丢番图不等式

本文证明了如果1相似文献   

一个素变数丢番图方程

证明了如果 １＜ｃ＜２５８／２３５,则素变数丢番图方程对充分大的 Ｎ是可解的,改进了 Ｋｕｍｃｈｅｖ和 Ｎｅｄｅｖａ的结果 １＜ｃ＜１２／１１．