Randomly Orthogonal (p, f)-factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this paper it is proved that every (mg m - 1,mf- m 1)-graph G has (g, f)-factorizations randomly κ-orthogonal to H and shown that the result is best possible.     

ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

1 IntroductionIn this paper we con8ider finite undirected simple graphs. Let G be a graph with vertexset V(G) and edge set E(G). Let g and f be two po8itive iuteger-valued functions defined onV(G) such that g(x) 5 f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanningsubgraph H of G satisfying g(x) 5 dH(x) 5 f(x) for each x E V(H). In particular, if G itselfis a (g, f)-factor, then G is called a (g, f)-grapl1. A subgrapl1 H of G is called an rmsubgraphif H has m edg…     

(g,f)-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE (mg,mf)-GRAPHS

§1　Preliminary and resultsAll graphs considered in this paper are finite graphs which may have multiple edgesbut no loops.Let G be a graph with vertex set V( G) and edge set E( G) .The degree of avertex x is denoted by d G( x) .The connectivity and edge-connectivity of G are denoted byκ( G) andλ( G) ,respectively.Letg and f be two positive integer-valued functions definedon vertex set V( G) such that g ( x)≤f ( x) .Then a ( g,f ) -factor of G is a spanningsubgraph H of G satisfying…     

A polynomial algorithm for finding (g,f)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

FRACTIONAL (g, f)-FACTORS OF GRAPHS

1 IntroductionThe graphs considered in this paper will be finite undirected graphs wllicll 11lay llavemultiple edges but no loops. Let G be a grapll with vertex set V(G) and edge set E(G). Fora vertex x of G, the degree of x in G is denoted by dG(z). Let g and f be two integer-valuedfunctions defined o11 V(G) such that 0 < g(z) 5 f(x) fOr all x E V(G). Then a (g, f)-factorof G is a spanning 8ubgraph F of G satisfying g(x) < dG(z) 5 f(x) for all x E V(F). Ifg(x) = f(x) for all x E V(…     

On the Factorizations of （mg, mf）-graph

Let G be an (mg, mf)-graph, where g and f are integer-valued functions defined on V(G) and such that 0≤g(x)≤f(x) for each x ∈ V(G). It is proved that(1) If Z ≠ , both g and f may be not even, G has a (g, f)-factorization, where Z = {x ∈ V(G): mf(x)-dG(x)≤t(x) or dG(x)-mg(x)≤ t(x), t(x)= f(x)-g(x)>0}.(2) Let G be an m-regular graph with 2n vertices, m≥n. If (P1, P2,..., Pr) is a partition of m, P1 ≡ m (mod 2), Pi ≡ 0 (mod 2), i = 2,..., r, then the edge set E(G) of G can be parted into r parts E1 , E2,...,Er of E(G) such that G[Ei] is a Pi-factor of G.     

（g,f）-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE （mg,mf）-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x). In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.     

The fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

符号混合控制问题的某些NP-完全性结果

Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.     

Topological entropy of a graph map

Let G be a graph and f : G → G be a continuous map. Denote by h(f), P(f), AP(f), R(f)and ω(x, f) the topological entropy of f, the set of periodic points of f, the set of almost periodic points of f, the set of recurrent points of f and the ω-limit set of x under f, respectively. In this paper,we show that the following statements are equivalent:(1) h(f) 0.(2) There exists an x ∈ G such that ω(x, f) ∩ P(f) = ? and ω(x, f) is an infinite set.(3) There exists an x ∈ G such that ω(x, f)contains two minimal sets.(4) There exist x, y ∈ G such that ω(x, f)-ω(y, f) is an uncountable set and ω(y, f) ∩ω(x, f) = ?.(5) There exist an x ∈ G and a closed subset A ? ω(x, f) with f(A) ? A such that ω(x, f)-A is an uncountable set.(6) R(f)-AP(f) = ?.(7) f |P(f)is not pointwise equicontinuous.     

Vertex-antimagic labelings of regular graphs

Let G = (V, E) be a finite, simple and undirected graph with p vertices and q edges. An (a, d)-vertex-antimagic total labeling of G is a bijection f from V (G) ∪ E(G) onto the set of consecutive integers 1, 2, . . . , p + q, such that the vertex-weights form an arithmetic progression with the initial term a and difference d, where the vertex-weight of x is the sum of the value f (x) assigned to the vertex x together with all values f (xy) assigned to edges xy incident to x. Such labeling is called super if the smallest possible labels appear on the vertices. In this paper, we study the properties of such labelings and examine their existence for 2r-regular graphs when the difference d is 0, 1, . . . , r + 1.     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Panconnectivity for interconnection networks with faulty elements

Let Go and G1 be two graphs with the same vertices. The new graph G（G0, G1; M） is a graph with the vertex set V（0o） ∪）V（G1） and the edge set E（Go） UE（G1） UM, where M is an arbitrary perfect matching between the vertices of Go and G1, i.e., a set of cross edges with one endvertex in Go and the other endvertex in G1. In this paper, we will show that if Go and G1 are f-fault q-panconnected, then for any f 〉 2, G（G0, G1; M） is （f ＋ 1）-fault （q ＋ 2）-panconnected.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).     

Extension of a quantized enveloping algebra by a Hopf algebra

Suppose that H is a Hopf algebra,and g is a generalized Kac-Moody algebra with Cartan matrix A =(aij)I×I,where I is an index set and is equal to either {1,2,...,n} or the natural number set N.Let f,g be two mappings from I to G(H),the set of group-like elements of H,such that the multiplication of elements in the set {f(i),g(i)|i ∈I} is commutative.Then we define a Hopf algebra Hgf Uq(g),where Uq(g) is the quantized enveloping algebra of g.     

Equality-constrained minimization of polynomial functions

This paper investigates the equality-constrained minimization of polynomial functions. Let R be the field of real numbers, and R[x1,..., xn] the ring of polynomials over R in variables x1,..., xn. For an f ∈ R[x1,..., xn] and a finite subset H of R[x1,..., xn], denote by V(f : H) the set {f( ˉα) | ˉα∈ Rn, and h( ˉα) =0, ? h ∈ H}. We provide an effective algorithm for computing a finite set U of non-zero univariate polynomials such that the infimum inf V(f : H) of V(f : H) is a root of some polynomial in U whenever inf V(f : H) = ±∞.The strategies of this paper are decomposing a finite set of polynomials into triangular chains of polynomials and computing the so-called revised resultants. With the aid of the computer algebraic system Maple, our algorithm has been made into a general program to treat the equality-constrained minimization of polynomials with rational coefficients.     

单圈图的无符号狄利克雷谱半径

Let G be a simple connected graph with pendant vertex set ?V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q(G). The signless Dirichlet eigenvalue is a real number λ such that there exists a function f ≠ 0 on V(G) such that Q(G)f(u) = λf(u) for u ∈ V_0 and f(u) = 0 for u ∈ ?V. The signless Dirichlet spectral radiusλ(G) is the largest signless Dirichlet eigenvalue. In this paper, the unicyclic graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with a given degree sequence are characterized.     

Topological Structure of Non-wandering Set of a Graph Map

Let G be a graph （i.e., a finite one-dimensional polyhedron） and f ： G → G be a continuous map. In this paper, we show that every isolated recurrent point of f is an isolated non-wandering point; every accumulation point of the set of non-wandering points of f with infinite orbit is a two-order accumulation point of the set of recurrent points of f; the derived set of an ω-limit set of f is equal to the derived set of an the set of recurrent points of f; and the two-order derived set of non-wandering set of f is equal to the two-order derived set of the set of recurrent points of f.     

On inclusion of permutation modules

Let H1,H2 be subgroups of a finite group G. Assume that G=∪i=1mH2yiH1=∪j=1nH1gjH1 and that y1=1,g1=1.Let Di be the set consisting of right cosets of H2 contained in H2yiH1 and let dj(j=1, . . . ,n) be the set consisting of right cosets contained in H1gjH1.We define the n×m matrix Mz(z=1, . . . ,m) whose columns and rows are indexed by Di and dj respectively and the (dk,Dl) entry is |Dzgk∩Dl|. Let M=(M1, . . . ,Mm). Assume that 1H1G and 1H2G are semisimple permutation modules of a finite group G. In this paper, by using the matrix M , we give some sufficient and necessary conditions such that 1H1G is isomorphic to a submodule of 1H2G.As an application, we prove Foulkes' conjecture in special cases.     

On the Tangent Bundle of a Hypersurface in a Riemannian Manifold

Let(Mn, g) and(Nn+1, G) be Riemannian manifolds. Let TMn and TNn+1 be the associated tangent bundles. Let f :(Mn,g) →(Nn+1,G) be an isometrical immersion with g = f*G, F =(f, df) :(TMn, ■) →(TNn+1, Gs) be the isometrical immersion with ■= F*Gs where (df)x: TxM → Tf(x)N for any x ∈M is the differential map, and Gs be the Sasaki metric on TN induced from G. This paper deals with the geometry of TMn as a submanifold of TNn+1 by the moving frame method. The authors firstly study the extrinsic geometry of TMn in TNn+1. Then the integrability of the induced almost complex structure of TM is discussed.