共查询到20条相似文献，搜索用时 0 毫秒
1.
Tom Eccles 《Journal of Graph Theory》2016,81(3):236-261
Given a graph and a colouring , the induced colour of a vertex v is the sum of the colours at the edges incident with v. If all the induced colours of vertices of G are distinct, the colouring is called antimagic. If G has a bijective antimagic colouring , the graph G is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than K2 are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least for some constant c; we improve on this result, proving the conjecture for graphs with average degree at least some constant d0. 相似文献
2.
给出了图Pm×Cn,I(Pm×Cn)和W(m,n)的序列标号.证明了图Pm×Cn,I(Pm×Cn)和W(m,n)(m≥1,n≥3且n为奇数)是序列图,从而也是调和图. 相似文献
3.
Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups. 相似文献
4.
Tong Li Zi-Xia Song Guanghui Wang Donglei Yang Cun-Quan Zhang 《Journal of Graph Theory》2019,90(1):46-53
A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to . A labeling of D is antimagic if no two vertices in D have the same vertex-sum, where the vertex-sum of a vertex for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz [On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232] initiated the study of antimagic labelings of digraphs, and conjectured that every connected graph admits an antimagic orientation, where an orientation D of a graph G is antimagic if D has an antimagic labeling. It remained unknown whether every disjoint union of cycles admits an antimagic orientation. In this article, we first answer this question in the positive by proving that every 2-regular graph has an antimagic orientation. We then show that for any integer , every connected, 2d-regular graph has an antimagic orientation. Our technique is new. 相似文献
5.
Let be a graph with a list assignment . Suppose a preferred color is given for some of the vertices; how many of these preferences can be respected when -coloring ? We explore several natural questions arising in this context, and propose directions for further research. 相似文献
6.
A graph is antimagic if there is a one‐to‐one correspondence such that for any two vertices , . It is known that bipartite regular graphs are antimagic and nonbipartite regular graphs of odd degree at least three are antimagic. Whether all nonbipartite regular graphs of even degree are antimagic remained an open problem. In this article, we solve this problem and prove that all even degree regular graphs are antimagic. 相似文献
7.
Daniel W. Cranston 《Journal of Graph Theory》2009,60(3):173-182
A labeling of a graph G is a bijection from E(G) to the set {1, 2,… |E(G)|}. A labeling is antimagic if for any distinct vertices u and v, the sum of the labels on edges incident to u is different from the sum of the labels on edges incident to v. We say a graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph other than K2 is antimagic. In this article, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 173–182, 2009 相似文献
8.
Danjun Huang & Dan Bao 《数学研究》2023,56(2):206-218
For a given simple graph $G = (V(G),E(G)),$ a proper total-$k$-coloring $c :V(G)∪E(G)→ {1,2,...,k}$ is neighbor sum distinguishing if $f(u)≠ f(v)$ for each edge $uv ∈ E(G),$ where $f(v) = sum_{wv∈E(G)} c(wv)+c(v).$ The smallest integer $k$ in such a coloring of $G$ is the neighbor sum distinguishing total chromatic number, denoted by $chi^{''}_{sum} (G).$ It has been conjectured that $chi ^{''}_{sum} (G) ≤ ∆(G)+3$ for any simple graph $G.$ Let $mad (G)=max{ frac{2|E(H)|}{ |V(H)|} :H⊆G}$ be the maximum average degree of $G.$ In this paper, byusing the famous Combinatorial Nullstellensatz, we prove $chi^{''} _{sum}(G) ≤ max{9,∆(G)+2}$ for any graph $G$ with $mad (G)<4.$ Furthermore, we characterize the neighbor sum distinguishing total chromatic number for every graph $G$ with $mad (G)<4$ and $∆(G)≥8.$ 相似文献
9.
设G是一个简单图,在G上当且仅当两个顶点的距离为2时增加一条边,所得的图称为G的平方,记作G2;在G上每个顶点都增加一条悬挂边所得的图称为G的冠,记作I(G).设Pn是n个顶点的路,本文给出了I(Pn2)、I(Fn)、F2n徊和I(Fn2)的序列标号. 相似文献
10.
Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′∑(G). Flandrin et al. proposed the following conjecture that χ′∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < (tfrac{{37}}{{12}}) and Δ(G) ≥ 7. 相似文献
11.
Ken-ichi KawarabayashiAtsuhiro Nakamoto Yoshiaki OdaKatsuhiro Ota Shinsei TazawaMamoru Watanabe 《Discrete Mathematics》2002,257(1):165-168
In this paper, we describe the structure of separable self-complementary graphs. 相似文献
12.
A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p2 and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010 相似文献
13.
Zelealem B. Yilma 《Journal of Graph Theory》2013,72(4):367-373
An antimagic labeling of a graph with m edges and n vertices is a bijection from the set of edges to the integers such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In this article, we discuss antimagic properties of graphs that contain vertices of large degree. We also show that graphs with maximum degree at least are antimagic. 相似文献
14.
15.
An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K2, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=pk vertices, where p is an odd prime and k is a positive integer that admits a Cp‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010. 相似文献
16.
JINJIANG YUAN 《运筹学学报》1998,(3)
1.IntroductionGraphsconsideredinthispaperarefiniteandsimple.FOragraphG,V(G)andE(G)denoteitssetofvenicesandedges,respectively.AbijectionwillbecalledalabellingofG.Letpbeapositiverealnumber.ForagivenlabellingTofagraphG,definethegndiscrepencya.(G,ac)ofTasTheobjectiveoftheminimum-p--sumproblemistofindalabelling7ofagraphGsuchthatac(G,T)isassmallaspossible.ThelabellingTminimizinga.(G,7)iscalledanoptimalHsumlabellingofG.Theminimumvalueiscalledtheminimum-psumofG.ItisshowninI31thattheminimum-… 相似文献
17.
An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K2, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010 相似文献
18.
Birk Eisermann 《Discrete Applied Mathematics》2011,159(17):2165-2169
Golumbic, Monma, and Trotter showed that every tolerance graph for which no vertex neighborhood is contained in another vertex neighborhood is a bounded tolerance graph. We strengthen this result by weakening the neighborhood condition. In this way, more tolerance graphs can be recognized as bounded. Our argument relies on a variation of the concept of “assertive vertices”. 相似文献
19.
LetG be a graph with vertex setV (G) and edge setE (G), and letg andf be two integer-valued functions defined on V(G) such thatg(x)⩽(x) for every vertexx ofV(G). It was conjectured that ifG is an (mg +m - 1,mf -m+1)-graph andH a subgraph ofG withm edges, thenG has a (g,f)-factorization orthogonal toH. This conjecture is proved affirmatively.
Project supported by the National Natural Science Foundation of China. 相似文献
20.
The vertex arboricity of a graph is the minimum number of colors required to color the vertices of such that no cycle is monochromatic. The list vertex arboricity is the list-coloring version of this concept. In this note, we prove that if is a toroidal graph, then ; and if and only if contains as an induced subgraph. 相似文献