Exact Solution to an Extremal Problem on Graphic Sequences with a Realization Containing Every 2-Tree on k Vertices

A simple graph G is a 2-tree if G=K_3,or G has a vertex v of degree 2,whose neighbors are adjacent,and G-v is a 2-tree.Clearly,if G is a 2-tree on n vertices,then |E(G)|=2 n-3.A non-increasing sequence π=(d_1,...,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.[Acta Math.Sin.Engl.Ser.,25,795-802(2009)] proved that if k≥2,n≥9/2 k~2+19/2 k and π=(d_1,...,d_n) is a graphic sequence with∑_(i=1)~n di(k-2)n,then π has a realization containing every 1-tree(the usual tree) on k vertices.Moreover,the lower bound(k-2)_n is the best possible.This is a variation of a conjecture due to Erdos and Sos.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] ~2+31[k/3]+12 and π=(d_1,...,d_n) is a graphic sequence with ∑_(i=1)~n d_imax{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].     

关于带宽极值问题的一些结果

本文研究的问题是确定f(p,B）的值，也就是给定顶点数p和带宽B，求满足最大度不超过B的连通图的最小边数，本文给出了一些f(p,B）的值及相应极图。     

关于蕴含_3C_l可图序列的极值问题(英文)

设σ（3Cl，n）是具有下述性质的最小正偶数，每个项和至少为σ（3Cl，n）的n项可图序列。都有一个实现含有长为3，4，…，l的圈．本文确定了当7≤l≤8且n≥l以及当l=9且n≥12时响σ（3Cl，n）的值．     

Finding a Solution to an Optimization Problem and an Application

Journal of Optimization Theory and Applications - In this paper, we obtain some best proximity point results on 0-complete partial metric spaces by introducing a new concept of mixed multivalued...     

3-Blocks with Abelian defect groups isomorphic to Z_{3^m } \times Z_{3^n }

Let G be a finite group and let p be a fixed prime number. Let B be a p-block of G with defect group D. In this paper, we give results on 3-blocks with abelian defect groups isomorphic to Z3m ×Z3n. We are particularly interested in the number of irreducible ordinary characters and the number of irreducible Brauer characters in the block. We calculate two important block invariants k（B） and l（B） in this case.     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

关于带宽极值问题的两个结果

本文研究的问题是确定ｅ＊（ｐ,Ｂ）的值,也就是确定顶点数为ｐ、带宽为Ｂ的连通图Ｇ的最小边数,本文给出当Ｂ＝ｐ＋３／２和Ｂ＝ｐ／２＋２时的精确结果。     

On Solution to an Optimal Shape Design Problem in 3-Dimensional Linear Magnetostatics

In this paper we present theoretical, computational, and practical aspects concerning 3-dimensional shape optimization governed by linear magnetostatics. The state solution is approximated by the finite element method using Nédélec elements on tetrahedra. Concerning optimization, the shape controls the interface between the air and the ferromagnetic parts while the whole domain is fixed. We prove the existence of an optimal shape. Then we state a finite element approximation to the optimization problem and prove the convergence of the approximated solutions. In the end, we solve the problem for the optimal shape of an electromagnet that arises in the research on magnetooptic effects and that was manufactured afterwards.     

On an Extremal Problem About the Arc-Length of Algebraic Polynomials

In this work we investigate polynomials of maximal (minimal) arc-length in the interval [−1, 1] amongst all monic polynomials of fixed degree n with n real zeros in [−1, 1].     

Solution to a Production Scheduling Problem with Fixed Costs

This study deals with a class of production scheduling problems characterized by a variable known demand and a fixed cost associated with each production run. The investigation originated from a problem encountered by a petroleum refinery. The refinery management was concerned with the high cost of manufacturing grease cans used for packaging of its grease products. This high cost resulted from the set-up cost incurred whenever the equipment (which was normally used to manufacture oil cans) was converted for manufacturing a relatively small quantity of grease cans with lithographed grade marking. The length of the production runs for making grease cans was severely restricted by a limited storage capacity. In order to meet the radically varying demand, the refinery frequently had to hand-stencil the grade on cans without grade marking. The problem faced by the management was to find a procedure for deciding when grease cans with lithographed grade marking should be produced so as to operate optimally.     

On an Extremal Problem About the Arc-Length of Algebraic Polynomials

In this work we investigate polynomials of maximal (minimal) arc-length in the interval [−1, 1] amongst all monic polynomials of fixed degree n with n real zeros in [−1, 1].     

On minimally 3-connected graphs on a surface

It is well known that the maximal size of minimally 3-connected graphs of order n ≥ 7 is 3n-9. In this paper, we shall prove that if G is a minimally 3-connected graph of order n, and is embedded in a closed surface with Euler characteristic χ, then G contains at most 2n- min {2, 2χ} edges. This bound is best possible for every closed surface.     

Constructing a 3-tree for a 3-connected matroid

In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M.     

An Extremal Problem on v-Partite Graphs

Let r, t, and v be positive integers with 2 ? t ? v. For a fixed graph G with t vertices, denote by Г (r, v, G) the class of all v-partite graphs H with vertex classes V_i, |V_i| = r (i =1, 2, ... , v) satisfying the following condition: For every t-subset {i₁, i₂, ... , i_t} of {1, 2, ... , v} there exists a subgraph of H isomorphic to G having exactly one vertex in each of the classes V_iτ, τ =1, 2, ... , t. Let cl(H) denote the clique number of H, i.e. the maximum order of a complete subgraph of H. We are interested in determining the value of the class parameter

$D(r,v,G)=\underset{H\in \Gamma (r,v,G)}{\min }cl(H)$

The main result is given the form of a Ramsey-type theorem (see Theorem 2.2). We shall show that for fixed r and G, D (r, v, G) tends to infinity when v tends to infinity if and only if χ(G) (the chromatic number of G) is greater than r. Some results concerning D(r, v, K_t), where K_t, is the complete graph on t vertices, are also given.     

An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences