共查询到20条相似文献，搜索用时 14 毫秒
1.
2.
A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ2 of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ3 of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γk) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011 相似文献
3.
The subconstituents of the isotropic unitary graphs over finite fields are shown to be quasi-strongly regular. In addition, the first subconstituent is shown to be co-edge regular and the second subconstituent is shown to be edge regular. The automorphism group of the second subconstituent is also determined. 相似文献
4.
We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph Kn is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs 相似文献
5.
Several results on the action of graph automorphisms on ends and fibers are generalized for the case of metric ends. This includes results on the action of the automorphisms on the end space, directions of automorphisms, double rays which are invariant under a power of an automorphism and metrically almost transitive automorphism groups. It is proved that the bounded automorphisms of a metrically almost transitive graph with more than one end are precisely the kernel of the action on the space of metric ends. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
6.
7.
《Journal of Graph Theory》2018,87(4):516-525
Let p be a prime greater than 5. We show that, while the generalized Petersen graphs of the form have cellular toroidal embeddings, they have no such embeddings having the additional property that a free action of a group on the graph extends to a cellular automorphism of the torus. Such an embedding is called a derived embedding. We also show that does have a derived embedding in the torus, and we show that for any odd q, each generalized Petersen graph of the form has a derived embedding in the Klein bottle, which has the same Euler characteristic as the torus. We close with some comments that frame these results in the light of Abrams and Slilaty's recent work on graphs featuring group actions that extend to spherical embeddings of those graphs. 相似文献
8.
Natalia P. Bondarenko 《Mathematical Methods in the Applied Sciences》2020,43(2):471-485
The Sturm-Liouville operator on the star-shaped graph is considered. We study its spectral properties, important for inverse problem theory. In particular, asymptotic formulas for the weight matrices are derived, by using contour integration. We also prove the Riesz-basis property for a special sequence of vector functions, constructed by the spectral data. 相似文献
9.
Let Fq be a finite field with q elements, n ≥ 2 a positive integer, and T(n, q) the semigroup of all n × n upper triangular matrices over Fq. The rank-decreasing graph 𝕋 of T(n, q) is a directed graph which has T(n, q) as vertex set, and there is a directed edge from A ∈ T(n, q) to B ∈ T(n, q) if and only if r(AB) < r(B). The zero-divisor graph 𝒯 of T(n, q), with vertex set of all nonzero zero-divisors of T(n, q) and there is a directed edge from a vertex A to a vertex B if and only if AB = 0, can be viewed as a subgraph of 𝕋. In [16], L. Wang has determined the automorphisms of the zero-divisor graph 𝒯 of T(n, q). In this article, by applying the main result of [17] we determine the automorphisms of the rank-decreasing graph 𝕋 of T(n, q). 相似文献
10.
Aleksander Malnič Dragan Marušič Primož Potočnik 《Journal of Algebraic Combinatorics》2004,20(1):99-113
Using covering graph techniques, a structural result about connected cubic simple graphs admitting an edge-transitive solvable group of automorphisms is proved. This implies, among other, that every such graph can be obtained from either the 3-dipole Dip3 or the complete graph K
4, by a sequence of elementary-abelian covers. Another consequence of the main structural result is that the action of an arc-transitive solvable group on a connected cubic simple graph is at most 3-arc-transitive. As an application, a new infinite family of semisymmetric cubic graphs, arising as regular elementary abelian covering projections of K
3,3, is constructed. 相似文献
11.
In the graph sharing game, two players share a connected graph G with nonnegative weights assigned to the vertices claiming and collecting the vertices of G one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole G has been claimed. It is proved that for any class of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class of planar graphs with an odd number of vertices), there is a constant such that the first player can secure at least the proportion of the total weight of G whenever . Known examples show that such a constant does no longer exist if any of the two conditions on the class (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision. 相似文献
12.
-algebras Jeong Hee Hong 《Proceedings of the American Mathematical Society》2005,133(1):115-126
We give conditions on an arbitrary directed graph for the associated Cuntz-Krieger algebra to be decomposable as a direct sum. We describe the direct summands as certain graph algebras.
13.
14.
A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We introduce a method for constructing near-polygonal graphs with 2-arc transitive automorphism groups. As special cases, we obtain several new infinite families of polygonal graphs. 相似文献
15.
Eric Swartz 《Journal of Combinatorial Theory, Series A》2010,117(6):783-789
A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary odd girth with 2-arc transitive automorphism groups. 相似文献
16.
17.
Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999 相似文献
18.
19.
Tibor Jordn 《Journal of Graph Theory》1999,31(3):179-193
Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999 相似文献
20.
Toru Hasunuma 《Discrete Applied Mathematics》2007,155(9):1141-1154
In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph Lk(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of Lk(G), it is shown that for any fixed directed graph G, Lk(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in Lk(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd. 相似文献