共查询到20条相似文献,搜索用时 15 毫秒
1.
Curtis R. Cook 《Discrete Mathematics》1973,4(2):129-138
A cubic lattice graph with characteristic n is a graph whose points can be identified with the ordered triplets on n symbols and two points are adjacent whenever the corresponding triplets have two coordinates in common. An L2 graph is a graph whose points can be identified with the ordered pairs on n symbols such that two points are adjacent if and only if the corresponding pairs have a common coordinate. The main result of this paper is two new characterizations and shows the relation between cubic lattice and L2 graphs. The main result also suggests a conjecture concerning the characterization of interchange graphs of complete m-partite graphs. 相似文献
2.
Sylwia Cichacz 《Central European Journal of Mathematics》2014,12(3):529-533
A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K m,n is a group distance magic graph if and only if n + m ? 2 (mod 4). 相似文献
3.
The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every . 相似文献
4.
This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form Kn × Km for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs. 相似文献
5.
Bruce Hedman 《Journal of Combinatorial Theory, Series B》1984,37(3):270-278
A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that vivj ∈ e(G) for vi ≠ vj if and only if |f(vi) ? f(vj)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K2(G), and inductively, denote K(Km?1(G)) by Km(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kn(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived. 相似文献
6.
Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km,n,r are developed. Using these, we obtain the chromatic equivalence classes for Km,n,n (where 1≤m≤n) and Km1,m2,m3 (where |mi−mj|≤3). In particular, it is shown that (i) Km,n,n (where 2≤m≤n) and (ii) Km1,m2,m3 (where |mi−mj|≤3, 2≤mi,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs Kn1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186]. 相似文献
7.
8.
Kexiang Xu 《Discrete Applied Mathematics》2011,159(15):1631-1640
The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices vi and vj in V(G) of G, recall that G+vivj is the supergraph formed from G by adding an edge between vertices vi and vj. Denote the Harary index of G and G+vivj by H(G) and H(G+vivj), respectively. We obtain lower and upper bounds on H(G+vivj)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained. 相似文献
9.
The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k2+3k+2)(b+1)2/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b2/2+(k+1)(k+i)b+k(k+2i−1)/2). 相似文献
10.
Chandan K. Dubey 《Discrete Applied Mathematics》2009,157(1):149-163
An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a1,b1),(a2,b2),…,(am,bm) such that G(V−{aj1,bj1,…,ajk,bjk}) is also an X-critical graph for arbitrary set of indices {j1,…,jk}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x1,y1),…,(xt,yt) such that xi,yi∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G. 相似文献
11.
Given a graph G, it is possible to attach positive and negative signs to its lines only, to its points only, or to both. The resulting structures are called respectively signed graphs, marked graphs and nets. The dual of each such structure is obtained by changing every sign in it. We determine all graphs G for which every suitable marked graph on G is self-dual (the M-dual graphs), and also the corresponding graphs G for signed graphs (S-dual) and for nets (N-dual.A graph G is M-dual if and only if G or ? is one of the graphs K2m, 2Km, mK2, Km + K2 or 2C4. The S-dual graphs are C6, 2C3, 2C4, 2K1n, 2nK2, K1,2n, nK1,2, K2n, K?n and all graphs obtained from these by the addition of isolated points. Finally, the only N-dual graph other than -K2n is 2K2. 相似文献
12.
A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K2,m (m may vary for each edge) by identifying u and v with the two vertices in K2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.
- 1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K2cq+1 and complete bipartite graphs Kmq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.
- 2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.
- 3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.
13.
Jianbing Niu 《Discrete Mathematics》2009,309(12):4095-4107
In this paper, we proved the following result: Let G be a (k+2)-connected, non-(k−3)-apex graph where k≥2. If G contains three k-cliques, say L1, L2, L3, such that |Li∩Lj|≤k−2(1≤i<j≤3), then G contains a Kk+2 as a minor. Note that a graph G is t-apex if G−X is planar for some subset X⊆V(G) of order at most t.This theorem generalizes some earlier results by Robertson, Seymour and Thomas [N. Robertson, P.D. Seymour, R. Thomas, Hadwiger conjecture for K6-free graphs, Combinatorica 13 (1993) 279-361.], Kawarabayashi and Toft [K. Kawarabayashi, B. Toft, Any 7-chromatic graph has K7 or K4,4 as a minor, Combinatorica 25 (2005) 327-353] and Kawarabayashi, Luo, Niu and Zhang [K. Kawarabayashi, R. Luo, J. Niu, C.-Q. Zhang, On structure of k-connected graphs without Kk-minor, Europ. J. Combinatorics 26 (2005) 293-308]. 相似文献
14.
Wayne Barrett 《Linear algebra and its applications》2011,434(10):2197-2203
Let G=(V,E) be a graph with V={1,2,…,n}. Denote by S(G) the set of all real symmetric n×n matrices A=[ai,j] with ai,j≠0, i≠j if and only if ij is an edge of G. Denote by I↗(G) the set of all pairs (p,q) of natural numbers such that there exists a matrix A∈S(G) with at most p positive and q negative eigenvalues. We show that if G is the join of G1 and G2, then I↗(G)?{(1,1)}=I↗(G1∨K1)∩I↗(G2∨K1)?{(1,1)}. Further, we show that if G is a graph with s isolated vertices, then , where denotes the graph obtained from G be removing all isolated vertices, and we give a combinatorial characterization of graphs G with (1,1)∈I↗(G). We use these results to determine I↗(G) for every complete multipartite graph G. 相似文献
15.
Toru Kojima 《Discrete Mathematics》2008,308(17):3770-3781
The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define hi=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that
16.
On bipartite zero-divisor graphs 总被引:1,自引:0,他引:1
A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3. 相似文献
17.
A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H0 which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np. 相似文献
18.
For every finite m and n there is a finite set {G1, …, Gl} of countable (m · Kn)-free graphs such that every countable (m · Kn)-free graph occurs as an induced subgraph of one of the graphs Gl © 1997 John Wiley & Sons, Inc. 相似文献
19.
It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M2(G)/m≥M1(G)/n, where M1 and M2 are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M2/(m−1)>M1/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results. 相似文献
20.
Ioan Tomescu 《Discrete Mathematics》2009,309(9):2745-788
The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P4, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K1+(K1,k+1∪(n−k−3)K1). 相似文献