双星图的IC-着色

研究了双星图的IC-着色问题,得到了双星图极大IC-着色的一些必要条件.利用这些必要条件,得到了双星图的极大IC-着色至多有两类着色方案,并确定了双星图在其中一种情况下的IC-指数.     

布尔矩阵平方根问题及其与图着色问题的关系

讨论了布尔矩阵平方根问题及其与图着色问题的关系.首先得到有平方根的布尔矩阵具有的一些性质;然后给出布尔矩阵存在平方根的一个充要条件;最后证明布尔矩阵的平方根问题可以转化为简单图的着色问题.     

平面图的循环色数与临界性

循环着色是普通着色的推广。本文中,我们研究了一类平面图的循环着色问题,并证明了这类平面图是循环色临界的,但不是普通色临界的,同时,我们还研究了循环着色与图G_k~d中的链之间的关系．     

Hopfield神经网络中的数学问题

Ｈｏｐｆｉｅｌｄ人工神经网络和多层网络模型中有许多基本的数学问题，其中，最重要的是存储容量的问题，即吸引子的个数，在以往的文章中，大多数都以概率模型为背景，本文从组合论的角度提供了几个问题，我们把Ｈｏｐｆｉｅｌｄ网络中的状态按连接矩阵所构成的变换分类，网络的容量就是类的个数，我们得出了一些基本结果，还有一些有意义的问题，如多层网络中的结果是否可交换等问题，还有待进一步研究。     

图的围长与无圈边色数之间的关系

对于一个图G的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在[1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．     

广义Peterson图的着色问题研究

图的着色问题是图论的重要研究内容之一,利用广义的Pólya定理和结合一些代数方法研究了广义Peterson图在不同约束条件下的着色问题,并给出了四种不同约束条件下的色多项式.     

关于图的全着色—一个综述

本文简要地综述了图的全着色的进展,给出了一些尚未解决的问题。     

一类具有分离变量的非线性离散系统的镇定控制器

在控制理论和控制工程中，镇定控制器的设计是一个经典问题。许多有关这个问题的结论一般都是针对线性系统。对于非线性系统，很少见到有构造性结果能用于控制工程中。本针对一类广泛的非线性控制系统，我们构造了一些控制器，这些判据在工程实际问题中将具有一定的指导意义。     

关于图D(Cn),C2n,C3n的星全色数

图G的一个k-全着色满足G的任何路长为2的点,边着色均不相同.我们称它为G的k-星全着色.图G的全部k-星全着色中最小的k称为图G的星全色数,记为Xn(G).讨论一些圈的星全染色问题,得到了图D(Cn)(n=0(mod 3)和n=0(mod 5)),C2n(n=0(mod 20)和n=0(mod 28))以及C3n(n=0(mod 28)和n=0(mod 36))的星全色数.     

关于图的具有标号型约束条件的正常全着色

数学的拓扑图可以自然地表示编码关系结构,也叫做拓扑图编码,这种关系结构在许多领域里得到应用.本文将图的全着色和图的边魔幻标号结合产生特殊的全着色,边魔幻tcn-纯全着色和均匀魔幻tcn-纯全着色.研究了树的边魔幻tcn-纯全着色,均匀魔幻tcn-纯全着色,以及具有极值性质的边魔幻全着色数,确定了特殊全着色在树上的精确着...     

Branch and cut algorithms for detecting critical nodes in undirected graphs

In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results.     

The bivariate Ising polynomial of a graph

In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.     

Compact cyclic edge-colorings of graphs

The paper is devoted to a model of compact cyclic edge-coloring of graphs. This variant of edge-coloring finds its applications in modeling schedules in production systems, in which production proceeds in a cyclic way. We point out optimal colorings for some graph classes and we construct graphs which cannot be colored in a compact cyclic manner. Moreover, we prove some theoretical properties of considered coloring model such as upper bounds on the number of colors in optimal compact cyclic coloring.     

Number theoretical aspects of primitive Egyptian labellings of the triangle

In the theory of graphs various graph labellings are known. In this paper we deal with number theoretical aspects of Egyptian labellings especially of triangles and introduce the concept of a maximal Egyptian labelling of a graph.     

Strictly chordal graphs are leaf powers

A fundamental problem in computational biology is the phylogeny reconstruction for a set of specific organisms. One of the graph theoretical approaches is to construct a similarity graph on the set of organisms where adjacency indicates evolutionary closeness, and then to reconstruct a phylogeny by computing a tree interconnecting the organisms such that leaves in the tree are labeled by the organisms and every organism appears as a leaf in the tree. The similarity graph is simple and undirected. For any pair of adjacent organisms in the similarity graph, their distance in the output tree, which is measured by the number of edges on the path connecting them, must be less than some pre-specified bound. This is known as the problem of recognizing leaf powers and computing leaf roots. Graphs that are leaf powers are known to be chordal. It is shown in this paper that all strictly chordal graphs are leaf powers and a linear time algorithm is presented to compute a leaf root for any given strictly chordal graph. An intermediate root-and-power problem, the Steiner root problem, is also examined.     

Expansions of the chromatic polynomial

The chromatic polynomial (or chromial) of a graph was first defined by Birkhoff in 1912, and gives the number of ways of properly colouring the vertices of the graph with any number of colours. A good survey of the basic facts about these polynomials may be found in the article by Read [3].It has recently been noticed that some classical problems of physics can be expressed in terms of chromials, and papers by Nagle [2], Baker [1], Temperley and Lieb [4], are concerned with methods of expanding the chromial for use in such problems. In this note we shall unify, simplify, and generalise their treatments, confining our attention to the theoretical basis of the methods.     

三类笛卡尔积图的关联色数

图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。     

Communication structure,trust and the free rider problem

Despite the recent wave of interest in the social and physical sciences regarding “complexity,” relatively title attention has been given to the logical foundation of complexity measurement. With this in mind, a number of fairly simple, “reasonable” axioms for the measurement of network complexity are here presented, and some of the implications of these axioms are considered. It is shown that the only family of graph complexity measures satisfying the “reasonable” axioms is of limited theoretical utility, and hence that those seeking more interesting measures of complexity must be willing to sacrifice at least one intuitively reasonable constraint. Several existing complexity measures are also described, and are differentiated from one another on an axiomatic basis. Finally, some suggestions are offered regarding future efforts at measuring graph complexity.     

关于图的强符号全控制数

图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了：（1）一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;（2）确定了圈、轮图、完全图、完全二部图的强符号全控制数的值.     

Decycling Number of Some Graphs

1.IntroductionInthispaper,weonlydiscusssimplegraph(withneithermulti-edgenorloop).TheterminologiesnotexplainedcanbeseeninII].Thecyclerankofagraphistheminimumnumberofedgesthatmustberemovedinordertoeliminateallofthecyclesinthegraph.IfGhaspvenices,qedges...