共查询到20条相似文献,搜索用时 31 毫秒
1.
F. M. Dong K. M. Koh K. L. Teo C. H. C. Little M. D. Hendy 《Journal of Graph Theory》2001,37(1):48-77
Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ???s(p,q) (resp., ??2?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph Kp,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? 2?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ?s(p,q) (resp., G ∈ ?? 2?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ???si(p+i,q?i) where max and si = s ? i(p?q+i) (resp., a subset of ??2?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from Kp,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001 相似文献
2.
The problem of vertex labeling with a condition at distance two in a graph, is a variation of Hale’s channel assignment problem, which was first explored by Griggs and Yeh. For positive integerp ≥q, the λ p,q -number of graph G, denoted λ(G;p, q), is the smallest span among all integer labellings ofV(G) such that vertices at distance two receive labels which differ by at leastq and adjacent vertices receive labels which differ by at leastp. Van den Heuvel and McGuinness have proved that λ(G;p, q) ≤ (4q-2) Δ+10p+38q-24 for any planar graphG with maximum degree Δ. In this paper, we studied the upper bound of λ p ,q-number of some planar graphs. It is proved that λ(G;p, q) ≤ (2q?1)Δ + 2(2p?1) ifG is an outerplanar graph and λ(G;p,q) ≤ (2q?1) Δ + 6p - 4q - 1 if G is a Halin graph. 相似文献
3.
Let G be a graph on p vertices with q edges and let r = q ? p = 1. We show that G has at most cycles. We also show that if G is planar, then G has at most 2r ? 1 = o(2r ? 1) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2r ? 1 cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255–264, 2008 相似文献
4.
D.Ž Djoković 《Journal of Combinatorial Theory, Series B》1973,15(2):167-173
Let G be a connected combinatorial graph of valency p + 1 where p is an odd prime. Assume that there exists a group of automorphisms A of G whose induced action on the s-arcs of G is regular (sharply transitive). If s ≥ 2 we prove that p must be a Mersenne prime, i.e., of the form p = 2n ? 1. In general we know that s ≤ 5 or s = 7. We obtain some partial results when s = 7. 相似文献
5.
By a graph we mean a finite undirected connected graph of order p, p ? 2, with no loops or multiple edges. A finite non-decreasing sequence S: s1, s2, …, sp, p ? 2, of positive integers is an eccentric sequence if there exists a graph G with vertex set V(G) = {v1, v2, …, vp} such that for each i, 1 ? i ? p, s, is the eccentricity of v1. A set S is an eccentric set if there exists a graph G such that the eccentricity ρ(v1) is in S for every v1 ? V(G), and every element of S is the eccentricity of some vertex in G. In this note we characterize eccentric sets, and we find the minimum order among all graphs whose eccentric set is a given set, to obtain a new necessary condition for a sequence to be eccentric. We also present some properties of graphs having preassigned eccentric sequences. 相似文献
6.
Abdo Y. Alfakih 《Discrete Applied Mathematics》2007,155(10):1244-1253
Let V={1,2,…,n}. A mapping p:V→Rr, where p1,…,pn are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in Rr, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in Rr is said to be dimensionally rigid iff there does not exist a framework G(q) in Rs for s?r+1, such that ∥qi-qj∥2=∥pi-pj∥2 for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p1,…,pn of the given r-configuration are in general position, is also investigated. 相似文献
7.
A. E. Zalesski 《Archiv der Mathematik》2013,100(3):221-230
The famous Gelfand–Graev character of a group of Lie type G is a multiplicity free character of shape ν G , where ν is a suitable degree 1 character of a Sylow p-subgroup and p is the defining characteristic of G. We show that, for an arbitrary non-abelian simple group G, if ν is a linear character of a Sylow p-subgroup of G such that ν G is multiplicity free, then G is isomorphic to either a group of Lie type in defining characteristic p, or to a group PSL(2, q), where either p = q + 1, or p = 2 and q + 1 or q ? 1 is a 2-power. 相似文献
8.
Let G = (V,E) be a finite connected weighted graph, and assume 1 ? α ? p ? q. In this paper, we consider the p-th Yamabe type equation ―?pu+huq―1 = λfuα―1 on G, where ?p is the p-th discrete graph Laplacian, h < 0 and f > 0 are real functions defined on all vertices of G. Instead of H. Ge’s approach [Proc. Amer. Math. Soc., 2018, 146(5): 2219–2224], we adopt a new approach, and prove that the above equation always has a positive solution u > 0 for some constant λ ∈ ?. In particular, when q = p, our result generalizes Ge’s main theorem from the case of α ? p > 1 to the case of 1 ? α ? p, It is interesting that our new approach can also work in the case of α ? p > 1. 相似文献
9.
Erich Prisner 《Results in Mathematics》1996,29(1-2):137-148
Given a graph-valued function ?, a graph G is called ? -periodic if there is some integer p ≥ 1 such that G is isomorphic to ?p(G). In this paper it is shown how to construct ?-periodic graphs, given essentially an embedding of a graph H as a subgraph of some iterated ?-graph ?p (H), provided ? obeys certain axioms. Then the results are applied to some graph-valued functions known in the literature. 相似文献
10.
Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K+((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K+((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3. 相似文献
11.
David Chillag 《Israel Journal of Mathematics》1975,21(1):50-53
LetG be a nonsolvable transitive permutation group of prime degreep. LetP be a Sylow-p-subgroup ofG and letq be a generator of the subgroup ofN G(P) fixing one point. Assume that |N G(P)|=p(p?1) and that there exists an elementj inG such thatj ?1qj=q(p+1)/2. We shall prove that a group that satisfies the above condition must be the symmetric group onp points, andp is of the form 4n+1. 相似文献
12.
R.M Weiss 《Journal of Combinatorial Theory, Series B》1974,16(3):229-233
Let G be a graph of valency d = 1 + prn with p prime and n < p. It is shown that if the automorphism group of G contains a subgroup A which acts as a regular permutation group on the set of s-arcs in G then s ≤ 7 and s ≠ 6; if d = pr + 1, r = 2r, v ≥ 1 an integer, p ≠ 2, then s = 1. 相似文献
13.
Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices Kk, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some Kk?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004 相似文献
14.
Alan Deckelbaum 《Journal of Number Theory》2009,129(6):1234-1245
Let G be a nonabelian group of order pq, where p and q are distinct odd primes. We analyze the minimum product set cardinality μG(r,s)=min|AB|, where A and B range over all subsets of G of cardinalities r and s, respectively. In this paper, we completely determine μG(r,s) in the case where G has order 3p and conjecture that this result can be extended to all nonabelian groups of order pq. We also prove that for every nonabelian group of order pq there exist 1?r,s?pq such that μG(r,s)>μZ/pqZ(r,s). 相似文献
15.
O. V. Besov 《Mathematical Notes》2014,96(3-4):326-331
We establish the embedding of the Sobolev space W p s (G) ? L q (G) for an irregular domain G in the case of a limit exponent under new relations between the parameters depending on the geometric properties of the domain G. 相似文献
16.
Alan P Sprague 《Journal of Combinatorial Theory, Series B》1977,22(3):199-206
For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s2 ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.) 相似文献
17.
For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph Gn,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions. 相似文献
18.
Toru Araki 《Discrete Applied Mathematics》2009,157(8):1677-1686
An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λp,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λp,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal. 相似文献
19.
A graph is called s-regular if its automorphism group acts regularly on the set of its s-arcs. In this paper, the s-regular cyclic or elementary abelian coverings of the Petersen graph for each s ? 1 are classified when the fibre-preserving automorphism groups act arc-transitively. As an application of these results, all s-regular cubic graphs of order 10p or 10p 2 are also classified for each s ? 1 and each prime p, of which the proof depends on the classification of finite simple groups. 相似文献
20.
A (p, q) graph G is edge-magic if there exists a bijective function f: V(G) ∪ E(G) → {1,2,…,p + q} such that f(u) + f(v) + f(uv) = k is a constant, called the valence of f, for any edge uv of G. Moreover, G is said to be super edge-magic if f(V(G)) = {1,2,…,p}. The question studied in this paper is for which graphs is it possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic? If it is possible for a given graph G, then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, μs(G) of G; otherwise we define it to be + ∞. 相似文献