Cycles and paths in bipartite tournaments with spanning configurations

We give necessary and sufficient conditions in terms of connectivity and factors for the existence of hamiltonian cycles and hamiltonian paths and also give sufficient conditions in terms of connectivity for the existence of cycles through any two vertices in bipartite tournaments.     

有向循环图寻径控制

有向循环图 G(N ;1 ,s)作为有向双环网的图论模型备受关注 .本文将图的点集分划为几个不交子集 ,找到任意节点对之间路径沿跳长为 1和跳长为 s的边数的上确界 .找到了判断节点对间最短路径的充要条件 ,利用点集的分布特征设计了一个最优寻径算法 .对双环网络的容错路径进行了深入研究 ,给出了容错直径公式 ,提出了一个最优容错路径算法 .     

二分图中度条件和k-因子的存在性

本文主要研究了二分图中任意一对距离为２的顶点的度数与ｋ－因子关系,给出了二分图有ｋ因子的若干充分条件,并说明这些条件是最好的可能,从而证明了Ｎｉｓｈｉｍｕｒａ提出的问题对二分图成立。     

Cycle decompositions of complete multigraphs

It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with λ edges joining each pair of distinct vertices into m‐cycles, or into m‐cycles and a perfect matching, are also sufficient. This result follows as an easy consequence of more general results which are obtained on decompositions of complete multigraphs into cycles of varying lengths. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:42‐69, 2010     

The maximum number of arc-disjoint arborescences in a tournament

In this article, we give the maximum number of arc-disjoint arborescences in a tournament or an oriented complete r-partite graph by means of the indegrees of its vertices.     

Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

Degree conditions on claws and modified claws for hamiltonicity of graphs

Ore presented a degree condition involving every pair of nonadjacent vertices for a graph to be hamiltonian. Fan [New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227] showed that not all the pairs of nonadjacent vertices are required, but only the pairs of vertices at the distance two suffice. Bedrossian et al. [A generalization of Fan's condition for hamiltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50] improved Fan's result involving the pairs of vertices contained in an induced claw or an induced modified claw. On the other hand, Matthews and Sumner [Longest paths and cycles in K_1,3-free graphs, J. Graph Theory 9 (1985) 269-277] gave a minimum degree condition for a claw-free graph to be hamiltonian. In this paper, we give a new degree condition in an induced claw or an induced modified claw ensuring the hamiltonicity of graphs which extends both results of Bederossian et al. and Matthews and Sumner.     

Three-valued Gauss periods,circulant weighing matrices and association schemes

Gauss periods taking exactly two values are closely related to two-weight irreducible cyclic codes and strongly regular Cayley graphs. They have been extensively studied in the work of Schmidt and White and others. In this paper, we consider the question of when Gauss periods take exactly three rational values. We obtain numerical necessary conditions for Gauss periods to take exactly three rational values. We show that in certain cases, the necessary conditions obtained are also sufficient. We give numerous examples where the Gauss periods take exactly three values. Furthermore, we discuss connections between three-valued Gauss periods and combinatorial structures such as circulant weighing matrices and three-class association schemes.     

Hamilton cycles in circulant digraphs with prescribed number of distinct jumps

Let G be a digraph that consists of a finite set of vertices V(G). G is called a circulant digraph if its automorphism group contains a |V(G)|-cycle. A circulant digraph G has arcs incident to each vertex i, where integers a_ks satisfy 0<a₁<a₂<a_j≤|V(G)|−1 and are called jumps. It is well known that not every G is Hamiltonian. In this paper we give sufficient conditions for a G to have a Hamilton cycle with prescribed distinct jumps, and prove that such conditions are also necessary for every G with two distinct jumps. Finally, we derive several results for obtaining G^′ with k, k≥2 distinct jumps if the corresponding G contains a Hamilton cycle with two distinct jumps.     

Distance Between Two Vertices of Maximum Matching Graphs

The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings which differ by exactly one edge. In this paper, we obtain a lower bound of distance between two vertices of maximum matching graph, and give a necessary and sufficient condition that the bound can be reached.     

二重(r1,r2)-循环矩阵求逆的一种新算法

本文给出了判定任意数域上二重（r1,r2)－循环矩阵非异性的一个充要条件，并提供了求这类矩阵逆的一种新方法。     

分数k-因子临界图的条件

设G是-个连通简单无向图,如果删去G的任意k个项点后的图有分数完美匹配,则称G是分数k-因子临界图．给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件．     

n维“格子笼”图的Hamilton问题

对n维"格子笼"图的Hamilton性进行了研究,得到了判定n维"格子笼"图是Hamilton图的一个非常简洁的充分必要条件.     

The Diameters of Some Transition Graphs Constructed from Hamilton Cycles

 A complete undirected graph of order n has Hamilton cycles. We consider the diameter of a transition graph whose vertices correspond to those Hamilton cycles and any of two vertices are adjacent if and only if the corresponding Hamilton cycles can be transformed each other by exchanging two edges. Moreover, we consider several transition graphs related to it. Received: November 4, 1999 Final version received: August 28, 2000     

On reachability mixed arborescence packing

As a generalization of Edmonds’ arborescence packing theorem, Kamiyama–Katoh–Takizawa (2009) provided a good characterization of directed graphs that contain arc-disjoint arborescences spanning the set of vertices reachable from each root. Fortier–Király–Léonard–Szigeti–Talon (2018) asked whether the result can be extended to mixed graphs by allowing both directed arcs and undirected edges. In this paper, we solve this question by developing a polynomial-time algorithm for finding a collection of edge and arc-disjoint arborescences spanning the set of vertices reachable from each root in a given mixed graph.     

Hyponormal Toeplitz Operators with Matrix-Valued Circulant Symbols

In this paper we are concerned with the hyponormality of Toeplitz operators with matrix-valued circulant symbols. We establish a necessary and sufficient condition for Toeplitz operators with matrix-valued partially circulant symbols to be hyponormal and also provide a rank formula for the self-commutator.     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

Hamiltonian Kneser Graphs

The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n. Received September 14, 1999     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.