Chromatic Index Critical Graphs of Even Order with Five Major Vertices

We prove that there does not exist any chromatic index critical graph of even order with exactly five vertices of maximum degree. This extends an earlier result of Chetwynd and Hilton who proved the same with five replaced by four or three.     

On maximum bipartite subgraphs

In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.     

On proportion polynomials

The proportion polynomials of maximum degree three and the proportion polynomials of classC ¹ of maximum degree five are determined. As an important tool, the class of the weak proportion polynomials (which includes the class of the proportion polynomials) is introduced and examined.     

A five-color theorem

In this note, we show that the edges and faces of any plane graph with maximum degree three can be simultaneously colored with five colors.     

2-connected coverings of bounded degree in 3-connected graphs

In a recent paper, Barnette showed that every 3-connected planar graph has a 2-connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2-connected spanning subgraphs of maximum degree five. In this paper, we show that every 3-connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2-connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc.     

Resource levelling for projects with schedule-dependent time windows

The paper presents polynomial heuristic procedures for different types of resource levelling problems for projects with minimum and maximum time lags between project activities. Both problems without and with explicit resource constraints are treated. Thus far, only pseudopolynomial heuristics for special resource levelling problems without maximum time lags and resource constraints have been proposed. An experimental performance analysis shows that the new heuristics approximately solve problem instances with up to 500 activities and five resources within reasonable computing time.     

Coloring Meyniel graphs in linear time

A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. We present a linear-time algorithm that colors optimally the vertices of a Meyniel graph and finds a clique of maximum size.     

微分学中不等式的证明

针对微分学不等式列出五种常用证明方法,即利用单调性证明法,利用拉格朗日中值定理证明法,利用最值证明法,利用泰勒公式证明法,和利用凹凸性证明法.实例说明每种方法的使用细节,以达到使初学者能尽快掌握微分学不等式证明的目的.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Conditions for the existence of continuous schedules of duration five

Each device must perform one operation with each of two demands assigned to it. The assignments are such that the maximum number of operations for one demand equals five, the partial precedence limitations are missing, simultaneous servicing of two or more demands by the same device or of one demand by two or more devices is forbidden, and the duration of each operation equals a unit. The necessary and sufficient conditions are obtained for the existence of a schedule of duration five conforming to the specified assignments and such that each device performs its operations during two consecutive intervals of unit duration. Hence follows the polynomial solvability of the problem under discussion.     

Computational investigations of maximum flow algorithms

The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O(n^1.5) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.     

Monotone Paths in Line Arrangements with a Small Number of Directions

We give subquadratic bounds on the maximum length of an x-monotone path in an arrangement of n lines with at most C log log n directions, where C is a suitable constant. For instance, the maximum length of an x-monotone path in an arrangement of n lines having at most ten slopes is O(n^67/34). In particular, we get tight estimates for the case of lines having at most five directions, by showing that previous constructions—(n^3/2) for arrangements with four slopes and (n^5/3) for arrangements with five slopes—due to Sharir and Matousek, respectively, are (asymptotically) best possible.     

The flat-maximum effect and generic linear scoring models: a test

Received on 1 July 1991. Predicting human behaviour patterns with linear correlationmodels has absorbed researchers for the past five decades. Althoughmost observers generally concede that humans are inferior tosuch models in combining information, linear scoring modelsare unfortunately, plagued by the flat-maximum effect or the‘curse of insensitivity’. As Lovie & Lovie(1986)observe: ‘The predictive ability of linear models is insensitiveto large variations in the size of regression weights and tothe number of predictors.’ In essence, seemingly differentscoringmodels tend to produce indistinguishable predictive outcomes. Since its demonstration by Dawes & Corrigan (1974), observershave cast the flat maximum in a decidedly negative light. Incontrast, Lovie & Lovie (1986) present a provocatively contrarianview of the flat maximum‘s positive potential. In thissame vein, we examine the predictive power of a generic credit-scoringmodel versus individual empirically derived systems. If, asWainer (1976) noted in regard to the flat maximum, ’itdon‘t make no nevermind’, generic credit-scoringmodels could provide cheaper alternatives to individual empiricallyderived models. During the period 1984–8, a series of linear credit-scoringmodels were developed for ten Southeastern U.S. credit unions.For each credit union, stepwise multiple regression was employedto select a subset of explanatory variables to be used in adiscriminant analysis. A generic credit-scoring equation wasdeveloped from the resulting discriminant analyses using weightedaverage coefficients from five systems. The predictive powerof the generic model was compared to the predictive power ofholdout sample of the five remaining credit-scoring models. In all cases, the generic model's performance was very closeto that of the empirically derived models. Thus, our findingssupport Lovie & Lovie's (1986) challenge to the conventionalwisdom that the flat maximum casts a pall on the successfulmodelling of judgement processes. Indeed, the flat maximum impliesa positive role for simpler, and hence cheaper, generic models.Although further research is needed, it should be possible todevelop hybrid models with generic cores that perform as wellas empirically derived linear models.     

A modified candecomp algorithm for fitting the latent class model: Implementation and evaluation

In this paper an implementation is discussed of a modified CANDECOMP algorithm for fitting Lazarsfeld's latent class model. The CANDECOMP algorithm is modified such that the resulting parameter estimates are non-negative and ‘best asymptotically normal’. In order to achieve this, the modified CANDECOMP algorithm minimizes a weighted least squares function instead of an unweighted least squares function as the traditional CANDECOMP algorithm does. To evaluate the new procedure, the modified CANDECOMP procedure with different weighting schemes is compared on five published data sets with the widely-used iterative proportional fitting procedure for obtaining maximum likelihood estimates of the parameters in the latent class model. It is found that, with appropriate weights, the modified CANDECOMP algorithm yields solutions that are nearly identical with those obtained by means of the maximum likelihood procedure. While the modified CANDECOMP algorithm tends to be computationally more intensive than the maximum likelihood method, it is very flexible in that it easily allows one to try out different weighting schemes.     

On the estimators of model-based and maximal reliability

Four estimators of the reliability for a composite score based on the factor analysis model and five estimators of the maximal reliability for the composite are presented. When the Wishart maximum likelihood is used for the estimation of the model parameters, it is shown that the five estimators of maximal reliability are the same. Asymptotic cumulants of the estimators and their logarithmic transformations are derived under arbitrary distributions with possible model misspecification. The theoretical results considering model misspecification when a model does not hold are shown to be closer to their simulated values than those neglecting model misspecification. Simulations of the confidence intervals using the normal approximation based on the asymptotically distribution-free theory and the asymptotic expansion by Hall’s method with variable transformation are performed.     

Mixture decomposition via the simulated annealing algorithm

This paper presents the problem of the evaluation of the maximum likelihood estimator, when the likelihood function has multiple maxima, using the stochastic algorithm called ‘simulated annealing’. Analysis of the particular case of the decomposition of a mixture of five univariate normal distributions shows the properties of this methodology with respect to the E—M algorithm. The results are compared considering some distance measures between the estimated distribution functions and the true one.     

Connected Q-integral graphs with maximum edge-degree less than or equal to 8

Graphs with integral signless Laplacian spectrum are called Q-integral graphs. The number of adjacent edges to an edge is defined as the edge-degree of that edge. The Q-spectral radius of a graph is the largest eigenvalue of its signless Laplacian. In 2019, Park and Sano [16] studied connected Q-integral graphs with the maximum edge-degree at most six. In this article, we extend their result and study the connected Q-integral graphs with maximum edge-degree less than or equal to eight. Further, we give an upper bound and a lower bound for the maximum edge-degree of a connected Q-integral graph with respect to its Q-spectral radius. As a corollary, we show that the Q-spectral radius of the connected edge-non-regular Q-integral graph with maximum edge-degree five is six, which we anticipate to be a key for solving the unsolved problem of characterizing such graphs.     

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Convex nonagons with five intervertex distances

The vertices of a convex planar nonagon determine exactly five distances if and only if they are nine vertices of a regular 10-gon or a regular 11-gon. This result has important ties to related concerns, including the maximum number of points in the plane that determine exactly five distances and, for each n7, the samllest t for which there exists a convex n-gon whose vertices determine t distances and are not all on one circle.     

Constructing the Spectrum of Packings and Coverings for the Complete Graph with Stars with up to Five Edges

The packing and covering problems have been considered for several classes of graphs. For instance, Bryant et. al. have investigated the packing problem for paths and cycles, and the packing and covering problems for 3-cubes. The packing and covering problems were settled for stars with up to six edges by Roditty. In this paper, for every possible leave graph (excess graph), we find a corresponding maximum packing (minimum covering) of the complete graph with stars with up to five edges.