图的割宽问题

本文建立了Ｈａｒｐｅｒ型割宽下界估计式，由此求出了轮形图Ｗｎ、完全二部图Ｋ（ｍ，ｎ）、圈幂Ｃｎｒ、格子图：Ｐｍ×Ｐｎ、Ｐｍ×Ｃｎ、Ｃｍ×Ｃｎ以及乘积图：Ｋｍ×Ｐｎ、Ｋｍ×Ｃｎ、Ｃｍｓ×Ｃｎｒ、Ｋｍ×Ｋｎ和强乘积图Ｐｍ　Ｐｎ的割宽。     

图的消去割宽问题

图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件：图中的边在一次性被搜索后立即堵塞,使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域. 在这个条件限制下,图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系,得到了一些特殊图类的消去割宽值.     

图的割宽极值问题

The problem studied in this paper is to determine e(p, C), the minimum size of a connected graph G with given vertex number p and cut-width C.     

图的割宽总是的度序列方法

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges is minimized. This paper presents an approach based on the degree sequence of G for determining the exact value of cutwidth of typical graphs (e. g. , n-cube,cater-pillars). Relations between the cutwidth and other graph-theoretic parameters are studied as well.     

Halin图$Q$-谱半径的最大值

The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.     

简单图圈基长度的最大值

图的圈基是图的一个重要结构,一个圈基的长度是该圈基中所有圈的长度之和,本讲座了简单图的圈基长度的最大值,得到了如下结果：设基圈数为k,顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时,C^*-kn;Ⅱ）若k=2,3,则对任意n≥4,C^*=kn-1,Ⅲ）若n(n≥5）为奇数,则对k(k≥4）的所有可能值,C^*=kn。     

一道最大值问题的延伸

题目设x,y,z为正数,求xy+2yz/x2+y2+z2的最大值.文[1]中潘继军老师巧用均值不等式解答了上面这个式子的最大值,并给出了3个变式和两个引理,读后很受启发.从教学的角度来讲,笔者认为文[1]中的变式还远远不够,文[1]的三个变式属于同一类型,解答方法有一定的局限性.本文用参数均值不等式的方法来解答这个题目的各种变     

四边形面积的最大值问题

给定一个四边形,其边长分别为a,b,c,d,在保持各边长度不变的情况下,这个四边形的形状是可以改变的．当它的形状改变时,其面积也相应的改变．本文讨论,在四边形形状改变的过程中（本文仅讨论凸四边形）,什么情况下它的面积有最大值？     

图的3限制性边割

3限制性边割将连通图分离成不连通图，使其各连通分支含有至少3个顶点．含3限制性边割的图在本文中得到刻划．     

直径不超过4的树的割宽

§ 1　IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see [2 ] ) .We shall follow the graph-theoretic terminology and notation of [1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996     

The Zarankiewicz problem in 3‐partite graphs

Let be a graph, be an integer, and write for the maximum number of edges in an ‐vertex graph that is ‐partite and has no subgraph isomorphic to . The function has been studied by many researchers. Finding is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing for . Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that and is odd, that is, for . In the cases of and , we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all and gives a better constant when . Finally, we point out an interesting connection between difference families from design theory and .     

Minimal cutwidth linear arrangements of abelian Cayley graphs

We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each order.     

An extremal bandwidth problem for bipartite graphs

This paper discusses the problem of finding the maximum number of edges E(m, n, B) in a bipartite graph having partite set sizes m and n and bandwidth B. Exact values for E(m, n, B) are found for many cases. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 278–289, 2000     

Long cycles in critical graphs

It is shown that any k‐critical graph with n vertices contains a cycle of length at least , improving a previous estimate of Kelly and Kelly obtained in 1954. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 193–196, 2000     

Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012