Even signings,signed switching classes,and (−1, 1)-matrices

In this paper, algebraic and combinatorial techniques are used to establish results concerning even signings of graphs, switching classes of signed graphs, and (?1, 1)-matrices. These results primarily deal with enumeration of isomorphism types, and determining whether there are fixed elements under the action of automorphisms. A formula is given for the number of isomorphism types of even signings of any fixed simple graph. This is shown to be equal to the number of isomorphism types of switching classes of signings of the graph. A necessary and sufficient criterion is found for all switching classes fixed by a given graph automorphism to contain signings fixed by that automorphism. It is determined whether this criterion is met for all automorphisms of various graphs, including complete graphs, which yields a known result of Mallows and Sloane. As an application, a formula is developed for the number of H-equivalence classes of (?1, 1)-matrices of fixed size. Independently, using Molien's theorem and following a suggestion of Cameron's, generating series for these numbers are given. As a final application, a necessary and sufficient condition that a square (?1, 1)-matrix be switching equivalent to a symmetric matrix is given.     

A Distance-Regular Graph with Intersection Array (5, 4, 3, 3; 1, 1, 1, 2) Does Not Exist

We prove that a distance-regular graph with intersection array (5, 4, 3, 3; 1, 1, 1, 2) does not exist. The proof is purely combinatorial and computer-free.     

Automorphisms of graphs with intersection arrays {60, 45, 8; 1, 12, 50} and {49, 36, 8; 1, 6, 42}

Automorphisms of distance-regular graphs are considered. It is proved that any graph with the intersection array {60, 45, 8; 1, 12, 50} is not vertex symmetric, and any graph with the intersection array {49, 36, 8; 1, 6, 42} is not edge symmetric.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.     

On automorphisms of a distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}

Prime divisors of orders of automorphisms and their fixed-point subgraphs are studied for a hypothetical distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}. It is shown that there are no arc-transitive distance-regular graphs with intersection array {35, 32, 1; 1, 4, 35}.     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

K_(1,n)-free图具有给定性质的[a,b]-因子的一个充分条件

图G称为K1,n-free图,如果它不含K1,n作为其导出子图.对K1,n-free图具有给定性质的[a,b]-因子涉及到最小度条件进行了研究,得到一个充分条件.     

两类树的独立集多项式的单峰性

研究了图的独立集多项式的单峰性,给出具有爪图结构的几类图的独立集多项式等价的无爪图,并在此基础上证明了两类具有爪图结构的树T(n,n+1,m)和T(I,i+1,k,j,j+1)的独立集多项式具有单峰性,从而为具有爪图结构的其它树的单峰性提供了一个证明方法.     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

Random packing by ρ-connected ρ-regular graphs

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each ρ-connected ρ-regular graph F with ρ > 1, there is a set (F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in (F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in (F).     

A 1-tough nonhamiltonian maximal planar graph

We construct a maxima' planar graph which is 1-tough but nonhamiltonian. The graph is an answer to Chvátal's question on the existence of such a graph.     

Equitable Coloring of Three Classes of 1-planar Graphs

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree Δ at least 15, 13 or 12 has an equitable Δ-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.     

On automorphisms of a distance-regular graph with intersection array {39, 36, 1; 1, 2, 39}

Possible prime-order automorphisms and their fixed-point subgraphs are found for a hypothetical distance-regular graph with intersection array {39, 36, 1; 1, 2, 39}. It is shownthat graphs with intersection arrays {15, 12, 1; 1, 2, 15}, {35, 32, 1; 1, 2, 35}, and {39, 36, 1; 1, 2, 39} are not vertex-symmetric.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

没有4至6-圈的平面图是(1,0,0)-可染的

设d₁, d₂,..., d_k 是k个非负整数. 若图G=(V,E) 的顶点集V可剖分成k个子集V₁, V₂,..., V_k,使得对i=1, 2,..., k 由V_i 所导出的子图G[V_i] 的最大度至多为d_i, 则称G是(d₁, d₂,..., d_k)-可染的. 著名的Steinberg 猜想断言, 每个既没有4-圈又没有5-圈的平面图是(0, 0, 0)-可染的. 对此猜想已经证明每个没有4 至7-圈的平面图是(0, 0, 0)-可染的, 但还没有发现有人证明每个没有4 至6-圈的平面图是(0, 0, 0)-可染的. 本文证明没有4 至6-圈的平面图是(1, 0, 0)-可染的.     

6度1-正则Cayley图

试图对6度1-正则Cayley图给一个完全分类．利用无核的概念将图自同构群归结到对称群S6的子群．然后根据1-正则图的性质构造出所有可能的具有非交换点稳定子群的无核6度1-正则Cayley图,进一步证明了构造出的图都是有核的,由此给出了这一类图的一个完全分类．     

The structure of 1-planar graphs

A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.     

Reduced 2-to-1 maps and decompositions of graphs with no 2-to-1 cut sets

A graph has an increasing ear decomposition if it can be constructed from a simple closed curve by attaching arcs in stages with the endpoints of each arc attached to different points so that at least one new branch point is formed at each stage. A reduced 2-to-1 map is a 2-to-1 map that does not have a restriction that is 2-to-1. A 2-to-1 cut set of a graph G is a finite subset B such that G⧹B has at least 2|B| components. A graph has an increasing ear decomposition if and only if it does not have a 2-to-1 cut set, and a graph is the image of a reduced 2-to-1 map if and only if it does not have a 2-to-1 cut set.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

On strong 1-factors and Hamilton weights of cubic graphs

A 1-factor M of a cubic graph G is strong if |M∩T|=1 for each 3-edge-cut T of G. It is proved in this paper that a cubic graph G has precisely three strong 1-factors if and only if the graph can be obtained from K₄ via a series of ↔Y operations. Consequently, the graph G admits a Hamilton weight and is uniquely edge-3-colorable.