具有第二大基指数的本原对称带号有向图的刻画

Recently, the primitive symmetric signed digraphs on n vertices with the maximum base 2n and the primitive symmetric loop-free signed digraphs on n vertices with the maximum base 2n-1 are characterized, respectively. In this paper, the primitive symmetric signed digraphs with loops on n vertices with the base 2n-1 are characterized, and then the primitive symmetric signed digraphs on n vertices with the second maximum base 2n-1 are characterized.     

固定悬挂点的三圈图的无号拉普拉斯谱半径

In this paper,we determine the unique graph with the largest signless Laplacian spectral radius among all the tricyclic graphs with n vertices and k pendant vertices.     

Counting rooted unicursal planar maps

This paper investigates the number of rooted unicursal planar maps and presents some formulae for such maps with four parameters： the numbers of nonrooted vertices and inner faces and the valencies of two odd vertices.     

ON STABILITY OF m-VARIATE C~1 INTERPOLATION

A.simplicial mesh(triangulation)is constructed that generalizes the two-dimensional 4-directionmesh to R~m.This mesh,with symmetric,shift-invariant values at the vertices,is shown to admit a boundedC~1 interpolant if and only if the alternating sum of the values at the vertices of any 1-cube is zero.This im-plies thai interpolation at the vertices of an m-dimensional,simplicial mesh by a C~1 piecewise polynomial ofdegree m+1 with one piece per simplex is unstable.     

On graphs with cut vertices and cut edges

Let G（n,k,t） be a set of graphs with n vertices,k cut edges and t cut vertices.In this paper,we classify these graphs in G（n,k,t） according to cut vertices,and characterize the extremal graphs with the largest spectral radius in G（n,k,t）.     

Bipartite graphs with the maximum sum of squares of degrees

In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.     

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

§ 1　IntroductionLet Km,nbe a complete bipartite graph with two vertex sets having m and n vertices,respectively.A subgraph F of Km,n is called a spanning subgraph of Km,nif F contains allthe vertices of Km,n.Itis clearthata graph with no isolated vertices is uniquely determinedby the setofits edges.So in this paper,we considera graph with no isolated vertices to bea setof2 -elementsets ofits vertices.Letk be a positive integer.A K1 ,k-factor of Km,nis aspanning subgraph F of Km,nsuch th…     

给定最大度的树的最大谱半径

In this paper, we characterize the trees with the largest Laplacian and adjacency spectral radii among all trees with fixed number of vertices and fixed maximal degree, respectively.     

A Graceful Algorithm of a Class of Trees

Let T be a tree with v vertices. It is said to be graceful if we can label the vertices with numbers 1,2,……,v in such a manner that the differences of any two adjacent vertices will again form the set {1,2,…,v-1}.Ringel conjectured, in1963, that every tree has a such labelling [1]. Ringel's conjecture remains unsettled. In this article, we shall investigate a class of graceful trees. Definition The,T_λ~((n)) is a tree with v_n vertices. Its vertices are v_i(j=0,1,…,n+1);v_(?)(j_o=1,2,…,n;j_1=1,2,…,k_1;……; j=1,2,…,k,≤λ), where λ,n,k_1,     

On the Monotonicity of (κ; g, h)-graphs

A (k;g)-graph is a k-regular graph with girth g. A (k;g)-cage is a (k;g)-graph with the least possible number of vertices. Let f(k;g) denote the number of vertices in a (k;g)-cage. The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. A fc-regular graph with girth pair (g,h) is called a (k;g,h)-graph. A (k;g,h)-cage is a (k;g,h)-graph with the least possible number of vertices. Let f(k;g,h) denote the number of vertices in a (k;g,h)-cage. In this paper, we prove the following strict inequality f(k;h-1,h)相似文献   

Efficient enumeration of the vertices of polyhedra associated with network LP's

Algorithms are given to list the vertices of polyhedra associated with network linear programs and their duals. Each algorithm has running time which is quadratic in the number of vertices of the polyhedron, and does not require that the polyhedron be either bounded or simple. The algorithms use characterizations of adjacent vertices in network and dual network LP's to perform an efficient traversal of the edge graph of the polyhedron. This contrasts with algorithms for enumerating the vertices of a general polyhedron, all of which have worst-case complexity which is exponential in the number of vertices of the polyhedron.     

On the P4-structure of perfect graphs. II. Odd decompositions

We prove that a graph is perfect if its vertices can be coloured by two colours in such a way that each induced chordless path with four vertices has an odd number of vertices of each colour. Using this result, we prove a decomposition theorem for perfect graphs; this theorem is defined in terms of the chordless path with four vertices.     

Integer Partitions from the Polyhedral Point of View

We characterize integer partitions that are convex combinations of two partitions, which connects vertices of the partition polytopes with Sidon sets and sum-free sets. We prove that all vertices of the partition polytope can be generated from a subset of support vertices with the use of two operations of merging parts. Application of either operation results in an adjacent vertex. We present also some numerical data on vertices.     

Smaller planar triangle-free graphs that are not 3-list-colorable

In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.     

匀称无圈超图的计数

研究了标号匀称无圈超图的计数, 得到了一般的$n$阶标号r-匀称(d)-森林和n阶标号r-匀称(d)-真森林的递推公式,并分别得到了包含和不包含独立点的$n$阶标号森林的计数显式.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with <Emphasis Type="Italic">n</Emphasis> vertices and <Emphasis Type="Italic">k</Emphasis> pendant vertices

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with n vertices and k pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with n vertices and k pendant vertices, respectively.     

A class of vertex-transitive digraphs,II

(1). We determine the number of non-isomorphic classes of self-complementary circulant digraphs with pq vertices, where p and q are distinct primes. The non-isomorphic classes of these circulant digraphs with pq vertices are enumerated. (2). We also determine the number of non-isomorphic classes of self-complementary, vertex-transitive digraphs with a prime number p vertices, and the number of self-complementary strongly vertex-transitive digraphs with p vertices. The non-isomorphic classes of strongly vertex-transitive digraphs with p vertices are also enumerated.     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.