共查询到20条相似文献,搜索用时 125 毫秒
1.
Eunjeong Yi 《数学学报(英文版)》2015,31(3):367-382
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. 相似文献
2.
黄庆学 《高校应用数学学报(英文版)》2003,18(3)
§ 1 IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi… 相似文献
3.
A lower bound on the total signed domination numbers of graphs 总被引:4,自引:0,他引:4
Xin-zhong LU Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2007,50(8):1157-1162
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. 相似文献
4.
WANG Tao&YU QingLin Institute of Applied Mathematics College of Mathematics Information Science Henan University Kaifeng China 《中国科学 数学(英文版)》2010,(5)
For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(resp.domination edge critical) and γ(G) = k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph. 相似文献
5.
The term (di)graph is employed to mean that a graph in question is either a directed graph or an undirected graph. The symbol G(p, r) represents the digraph defined by Chao[1]:V(G(p,r)) = Zp, E(G(p,r)) = {(x,y)|x - y ∈ Hr}, where p is a prime, r is a positive divisor of p - 1 and Hr is the unique subgroup of order r in Aut(Zp). 相似文献
6.
The term (di)graph is employed to mean that a graph in question is either a directed graph or an undirected graph.The symbol G(p,r)represents the digraph defined by Chao: V(G(p,r))=Zp,E(G(p,r))={(x,y)|x-y∈Hr},where P is a prime,r is a positive divisor of P-1 and Hr is the unique subgroup of order r in Aut(Zp).A Cayley graph (?)=Cay(G,S)is called imprimitive if A=Aut((?))acts imprimitively on V((?)).Let (?)=Cay(G,S)be a connected imprimitive arc-transitive graph on G=Z×Z,B={B0,B1,…,Bp-1}the complete block system of A=Aut((?))on V((?))=G and K the kernel of A on B.Then obviously K≠1. 相似文献
7.
1. IntroductionLet G be a finite group and S a subset of G such that S--1 ~ S, and 1 f S. The Cayleygraph Cay (G, S) is defined as the simple graph with V ~ G, and E = {glgZ I g,'g, or g,'g,6 S, gi, gi E G}. Cay (G, S) is vertex-transitive, and it is connected if and only if (S) = G,i.e. S is a generating set of G[1]. If G = Zn, then Cay (Zn, S) is called a circulant graph. Ithas been proved that any connected Cayley graph on a finite abelian group is hamiltonianl2].Furthermore, … 相似文献
8.
高随祥 《应用数学学报(英文版)》2001,17(1):129-139
1. IntroductionA gash G is an ordered pair of disjoillt sets (V, E) such that E is a subset of the setof unordered pairs of V, where the sets V and E are finite. The set V is cajled the setof venices and E is called the set of edges. They are usually denoted by V(G) and E(C),respectively. An edge (x, y) is said to join the venices x and y, and is sometimes denotedby xo or ear. By our definition, a graph does not colltain any loOP, neither does it colltainmultiple edges.Other terms undef… 相似文献
9.
Let N denote the set of positive integers. The sum graph G^+(S) of a finite subset S belong to N is the graph (S, E) with uv ∈ E if and only if u + v ∈ S. A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S belong to N. By using the set Z of all integers instead of N, we obtain the definition of the integral sum graph. A graph G = (V, E) is a mod sum graph if there exists a positive integer z and a labelling, λ, of the vertices of G with distinct elements from {0, 1, 2,..., z - 1} so that uv ∈ E if and only if the sum, modulo z, of the labels assigned to u and v is the label of a vertex of G. In this paper, we prove that flower tree is integral sum graph. We prove that Dutch m-wind-mill (Dm) is integral sum graph and mod sum graph, and give the sum number of Dm. 相似文献
10.
PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS 总被引:5,自引:0,他引:5
Yang Aifeng Yuan Jinjiang Dept. of Appl. Math. South China Univ. of Tech. Guangdong China. Dept. of Math. Zhengzhou Univ. Henan China. 《高校应用数学学报(英文版)》2004,19(3):245-251
§1 IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )… 相似文献
11.
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs. 相似文献
12.
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1(L) = 2λ1 (D), and that for a connected graph G and its line graph L, if one of κ1 (L) and λ(G) exists, then κ1(L) = λ2(G). This paper determines that κ1(B(d, n) is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1(K(d, n)) is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K(2, 2). It then follows that B(d,n) and K(d, n) are both super connected for any d ≥ 2 and n ≥ 1. 相似文献
13.
Jian Wang 《高校应用数学学报(英文版)》2008,23(3):345-350
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that (1) m ≤ kn, (2) n ≤ km, (3) km-n = kn-m ≡ 0 (mod (k^2- 1)) and (4) λ(km-n)(kn-m) ≡ 0 (mod k(k- 1)(k^2 - 1)(m + n)). 相似文献
14.
Jian-pingOu Fu-jiZhang 《应用数学学报(英文版)》2003,19(3):505-510
An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp. 相似文献
15.
Some results on R
2-edge-connectivity of even regular graphs 总被引:1,自引:0,他引:1
XuJunming 《高校应用数学学报(英文版)》1999,14(3):366-370
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given. 相似文献
16.
WANG Yingqian Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2006,49(6):791-799
The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis. 相似文献
17.
Yosef Stein 《Israel Journal of Mathematics》1989,68(1):109-122
LetK be an algebraically closed field of characteristic zero. ForA ∈K[x, y] let σ(A) = {λ ∈K:A − λ is reducible}. For λ ∈ σ(A) letA − λ = ∏
i=1
n(λ)
A
iλ
k
μ whereA
iλ are distinct primes. Let ϱλ(A) =n(λ) − 1 and let ρ(A) = Σλɛσ(A)ϱλ(A). The main result is the following:
Theorem.If A ∈ K[x, y] is not a composite polynomial, then ρ(A) < degA. 相似文献
18.
Gordan Savin 《Israel Journal of Mathematics》1992,80(1-2):195-205
LetG andH ⊂G be two real semisimple groups defined overQ. Assume thatH is the group of points fixed by an involution ofG. Letπ ⊂L
2(H\G) be an irreducible representation ofG and letf επ be aK-finite function. Let Γ be an arithmetic subgroup ofG. The Poincaré seriesP
f(g)=ΣH∩ΓΓ
f(γ{}itg) is an automorphic form on Γ\G. We show thatP
f is cuspidal in some cases, whenH ∩Γ\H is compact.
Partially supported by NSF Grant # DMS 9103608. 相似文献
19.
E. Ballico 《Annali dell'Universita di Ferrara》1999,45(1):123-125
Fix integersg, k andt witht>0,k≥3 andtk<g/2−1. LetX be a generalk-gonal curve of genusg andR∈Pic
k
(X) the uniqueg
k
1
onX. SetL:=K
X⊗(R
*)⊗t.L is very ample. Leth
L:X→P(H
0(X, L)*) be the associated embedding. Here we prove thath
L(X) is projectively normal. Ifk≥4 andtk<g/2−2 the curveh
L(X) is scheme-theoretically cut out by quadrics.
The author was partially supported by MURST and GNSAGA of CNR (Italy). 相似文献
20.
Definen
K
(λ) to be either ω, or the number of non-isomorphic models inK having cardinality α, whichever cardinal is larger. This paper contains a proof that for a congruence modular variety ⋎ of
algebras of countable similarity type, there are only six possible functionsn
⋎. It is also proved that ifn
K
(λ)≠2λ for some λ, andK is a universal Horn class of models for a countable language, thenK must satisfy two conditions, one of which is quite restrictive and requires that the members ofK are all in a certain sense Abelian.
Presented by B. Jonsson. 相似文献