共查询到20条相似文献,搜索用时 0 毫秒
1.
An antimagic labeling of a digraph with vertices and arcs is a bijection from the set of arcs of to such that all oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation. 相似文献
2.
A of a digraph with arcs is a bijection from the set of arcs of to . A labeling of is if no two vertices in have the same vertex-sum, where the vertex-sum of a vertex for a labeling is the sum of labels of all arcs entering minus the sum of labels of all arcs leaving . An orientation of a graph is if has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2-regular graphs with more than two odd components. We show that every 2-regular graph with odd components has an antimagic orientation. And we show that each 2-regular graph with odd components admits an antimagic orientation if each odd component has at least vertices with . 相似文献
3.
4.
《Discrete Mathematics》2020,343(12):112123
5.
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. 相似文献
6.
7.
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. 相似文献
8.
A class of antimagic join graphs 总被引:1,自引:0,他引:1
A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic. 相似文献
9.
In [Pasotti, A., On d-graceful labelings, to appear on Ars Combin] a d-divisible α-labeling is defined as a generalization of the classical one of Rosa (see [Rosa, A., On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349–355]) and, similarly to the classical case, it is proved that there exists a link between d-divisible α-labelings of a graph Γ and cyclic Γ-decompositions. In [Benini, A., and Pasotti, A., Decompositions of complete multipartite graphs via generalized graceful labelings, submitted. (arXiv:1210.4370)] we have dealt with the existence of d-divisible α-labelings of caterpillars and certain classes of cycles and hairy cycles and the resulting possible decompositions. 相似文献
10.
11.
The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P(4k, k) and hence a lower bound for the crossing number of P(4k, k). In addition, an upper bound for the crossing number of P(4k, k) is also given. 相似文献
12.
13.
Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph G≠K2 is 0‐antimagic. On the other hand, there are connected graphs G≠K2 which are not weighted‐1‐antimagic. It is unknown whether every connected graph G≠K2 is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph G≠K2 on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
14.
We determine the automorphism group of the generalized orthogonal graph GO2v+δ(q, m, G) over Fq of characteristic 2, where 1 〈 m 〈 v. 相似文献
15.
For a positive integer d, the usual d‐dimensional cube Qd is defined to be the graph (K2)d, the Cartesian product of d copies of K2. We define the generalized cube Q(Kk, d) to be the graph (Kk)d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(Kk, di), where k is a power of a prime, n and j are positive integers with j ≤ n, and the di may be different in different factors. We also use these results to partially settle a problem of Kotzig on Qd‐factorizations of Kn. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000 相似文献
16.
Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained. 相似文献
17.
18.
程辉 《纯粹数学与应用数学》2001,17(3):197-200,213
讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V(X)]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。 相似文献
19.
Yongxi Cheng 《Discrete Mathematics》2008,308(24):6441-6448
An antimagic labeling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges 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 the same vertex. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel [N. Hartsfield, G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K2, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference COCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic. 相似文献
20.
Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110]. 相似文献