Balls,bins, and embeddings of partial k-star designs

Define a $k$-star to be the complete bipartite graph $K_{1,k}$. In a 2014 article, Hoffman and Roberts prove that a partial $k$-star decomposition of $K_n$ can be embedded in a $k$-star decomposition of $K_{n+s}$ where $s$ is at most $7k?4$ if $k$ is odd and $8k?4$ if $k$ is even. In our work, we offer a straightforward construction for embedding partial $k$-star designs and lower these bounds to $3k?2$ and $4k?2$, respectively.     

二部图的距离k次方和问题

本文定义S_k（G）为G中所有点对之间距离的k次方之和.利用顶点划分的方法得到了直径为d的n顶点连通二部图S_k（G）的下界,并确定了达到下界所对应的的极图.     

图的割宽极值问题

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.     

最大边数的Cordial图的构造

对于n阶Cordial图G，本给出G的边数的上确界e^*，并给出边数达到e^*的Cordial图的构造。     

谱半径前五位的$n$阶拟树图

A connected graph G =(V, E) is called a quasi-tree graph, if there exists a vertex v_0 ∈ V(G) such that G-v_0 is a tree. Liu and Lu [Linear Algebra Appl. 428(2008) 2708-2714] determined the maximal spectral radius together with the corresponding graph among all quasi-tree graphs on n vertices. In this paper, we extend their result, and determine the second to the fifth largest spectral radii together with the corresponding graphs among all quasi-tree graphs on n vertices.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

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     

图的割宽最大值问题

§ 1　IntroductionThe cutwidth minimization problem for graphs arises from the circuitlayout of VLSIdesigns[1 ] .Chung pointed outthatthe cutwidth often corresponds to the area of the layoutin array layout in VLSI design[2 ] .In the layout models,the cutwidth problem deals withthe number of edges passing over a vertex when all vertices are arranged in a path.For agraph G with vertex set V(G) and edge set E(G) ,a labeling of G is a one-to-one mapping ffrom V(G) to the integers.The cutwid…