共查询到20条相似文献,搜索用时 390 毫秒
1.
Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum. 相似文献
2.
Let G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define if v⁄∈S, and wS(v)=2 if v∈S. If, for each v∈V(G), we have wS(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γe(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γe(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then . 相似文献
3.
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 of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑v∈Vf(v). The Roman domination number of a graph G, denoted by γR(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γR(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22]. 相似文献
4.
A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V0,V1,V2) of V(G), where Vi={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V0 implies |N(x)∩V2|≤1 and x∈V1∪V2 implies that |N(x)∩V2|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by uR(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter. 相似文献
5.
Let G=(V,E) be a simple graph with vertex degrees d1,d2,…,dn. The Randi? index R(G) is equal to the sum over all edges (i,j)∈E of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(G). To prove it, we also show that if v∈V is a vertex of minimum degree δ of G, G−v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G, then . 相似文献
6.
Nikolaos D. Atreas 《Journal of Mathematical Analysis and Applications》2011,377(2):841-852
Let V? be a closed subspace of L2(R) generated from the integer shifts of a continuous function ? with a certain decay at infinity and a non-vanishing property for the function Φ†(γ)=∑n∈Z?(n)e−inγ on [−π,π]. In this paper we determine a positive number δ? so that the set {n+δn}n∈Z is a set of stable sampling for the space V? for any selection of the elements δn within the ranges ±δ?. We demonstrate the resulting sampling formula (called perturbation formula) for functions f∈V? and also we establish a finite reconstruction formula approximating f on bounded intervals. We compute the corresponding error and we provide estimates for the jitter error as well. 相似文献
7.
Harris Kwong 《Discrete Mathematics》2008,308(23):5522-5532
Let G be a graph with vertex set V and edge set E, and let A be an abelian group. A labeling f:V→A induces an edge labeling f∗:E→A defined by f∗(xy)=f(x)+f(y). For i∈A, let vf(i)=card{v∈V:f(v)=i} and ef(i)=card{e∈E:f∗(e)=i}. A labeling f is said to be A-friendly if |vf(i)−vf(j)|≤1 for all (i,j)∈A×A, and A-cordial if we also have |ef(i)−ef(j)|≤1 for all (i,j)∈A×A. When A=Z2, the friendly index set of the graph G is defined as {|ef(1)−ef(0)|:the vertex labelingf is Z2-friendly}. In this paper we completely determine the friendly index sets of 2-regular graphs. In particular, we show that a 2-regular graph of order n is cordial if and only if n?2 (mod 4). 相似文献
8.
Fuqing Gao 《Journal of Mathematical Analysis and Applications》2003,285(1):1-7
Let X0,X1,… be i.i.d. random variables with E(X0)=0, E(X20)=1 and E(exp{tX0})<∞ for any |t|<t0. We prove that the weighted sums V(n)=∑j=0∞aj(n)Xj, n?1 obey a moderately large deviation principle if the weights satisfy certain regularity conditions. Then we prove a new version of the Erdös-Rényi-Shepp laws for the weighted sums. 相似文献
9.
We deal with MAXH0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ0+1)/(B+2+ν0), where B=maxv∈VdG(v), δ0=minv∈V(H0)dH0(v) and ν0=(|V(H0)|+1)/δ0. Next, we show that this ratio rises up to 3/(B+1) when H0=K3. Finally, we provide hardness results for MAXK3-FREE PARTIAL SUBGRAPH. 相似文献
10.
A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V1∪?∪Vr is called a balanced decomposition if Vi is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V1∪?∪Vr with |Vi|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied. 相似文献
11.
H. E. Moses 《Studies in Applied Mathematics》1979,60(2):177-181
Let us consider the one-dimensional Schrödinger equation with the scattering potential V(x)=2δ(x) and corresponding reflection coefficient b(k)=?i/(k + i). The potential satisfies a theorem of Deift and Trubowitz which states that non-negative measurable potentials V(x) satisfying a certain range condition have reflection coefficients b(k) such that b(0)=?1. We rescale the reflection coefficient for V(x)=2δ(x) by writing b(k)=?iv/(k + 1) where 0<v<1. It is shown how V(x) changes with v, through the use of the Gelfand-Levitan equation. This example illustrates how sensitive the potential is to rescaling of the reflection coefficient. In particular, the rescaling leads to a negative portion of V(x), as is expected from the Deift-Trubowitz theorem. The example of this paper will be used in a later paper to illustrate the nature of bounds on potentials obtained through the use of variational principles. 相似文献
12.
Vesselin Petkov 《Journal of Functional Analysis》2006,235(2):357-376
We obtain global Strichartz estimates for the solutions u of the wave equation for time-periodic potentials V(t,x) with compact support with respect to x. Our analysis is based on the analytic properties of the cut-off resolvent Rχ(z)=χ(U−1(T)−zI)ψ1, where U(T)=U(T,0) is the monodromy operator and T>0 the period of V(t,x). We show that if Rχ(z) has no poles z∈C, |z|?1, then for n?3, odd, we have a exponential decal of local energy. For n?2, even, we obtain also an uniform decay of local energy assuming that Rχ(z) has no poles z∈C, |z|?1, and Rχ(z) remains bounded for z in a small neighborhood of 0. 相似文献
13.
Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N0 is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v1)=1 and (2) for each i with 1?i<n, c(vi+1) is the smallest positive integer p such that F(vj,vi+1,|c(vj)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and . 相似文献
14.
Margit Voigt 《Discrete Mathematics》2009,309(15):4926-4930
Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K4 then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set. 相似文献
15.
Ali Behtoei Behnaz Omoomi 《Discrete Applied Mathematics》2011,159(18):2214-2221
Let c be a proper k-coloring of a connected graph G and Π=(C1,C2,…,Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|x∈Ci},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χL(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χL(KG(n,2))=n−1 for all n≥5. Then, we prove that χL(KG(n,k))≤n−1, when n≥k2. Moreover, we present some bounds for the locating chromatic number of odd graphs. 相似文献
16.
Carl Johan Casselgren 《European Journal of Combinatorics》2012,33(2):168-181
Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n. 相似文献
17.
Let f be a permutation of V(G). Define δf(x,y)=|dG(x,y)-dG(f(x),f(y))| and δf(G)=∑δf(x,y) over all the unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δf(G) among all the permutations f of V(G). The permutation f with δf(G)=π(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles Cn and we prove that π(Cn)=4⌊n/2⌋-4, moreover, we obtain the set of near automorphisms of Cn. 相似文献
18.
Vladimir Nikiforov 《Linear algebra and its applications》2006,414(1):347-360
Let G be a graph with n vertices and m edges and let μ(G) = μ1(G) ? ? ? μn(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑u∈V(G)∣d(u)-2m/n∣. We prove that
19.
Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard. 相似文献
20.
Kamal Boussaf 《Bulletin des Sciences Mathématiques》2010,134(1):44
Let K be a complete ultrametric algebraically closed field. We investigate several properties of sequences (an)n∈N in a disk d(0,R−) with regards to bounded analytic functions in that disk: sequences of uniqueness (when f(an)=0∀n∈N implies f=0), identity sequences (when limn→+∞f(an)=0 implies f=0) and analytic boundaries (when lim supn→∞|f(an)|=‖f‖). Particularly, we show that identity sequences and analytic boundary sequences are two equivalent properties. For certain sequences, sequences of uniqueness and identity sequences are two equivalent properties. A connection with Blaschke sequences is made. Most of the properties shown on analytic functions have continuation to meromorphic functions. 相似文献