Neighbor product distinguishing total colorings

A total-[k]-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\rightarrow \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let f(v) denote the product of the color of a vertex v and the colors of all edges incident to v. A total-[k]-neighbor product distinguishing-coloring of G is a total-[k]-coloring of G such that \(f(u)\ne f(v)\), where \(uv\in E(G)\). By \(\chi ^{\prime \prime }_{\prod }(G)\), we denote the smallest value k in such a coloring of G. We conjecture that \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that the conjecture holds for complete graphs, cycles, trees, bipartite graphs and subcubic graphs. Furthermore, we show that if G is a \(K_4\)-minor free graph with \(\Delta (G)\ge 4\), then \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+2\).     

Algebraic connectivity of an even uniform hypergraph

We generalize Laplacian matrices for graphs to Laplacian tensors for even uniform hypergraphs and set some foundations for the spectral hypergraph theory based upon Laplacian tensors. Especially, algebraic connectivity of an even uniform hypergraph based on Z-eigenvalues of the corresponding Laplacian tensor is introduced and its connections with edge connectivity and vertex connectivity are discussed.     

Generalized acyclic edge colorings via entropy compression

An r-acyclic edge coloring of a graph G is a proper edge coloring such that any cycle C has at least \(\min \{|C|,r\}\) colors. The least number of colors needed for an r-acyclic edge coloring of G is called the r-acyclic edge chromatic number or the r-acyclic chromatic index of G, denoted by \(A'_{r}\left( G\right) \). In this paper, we study the r-acyclic edge chromatic number with \(r\ge 4\) and prove that \(A'_{r}\left( G\right) \le 2\Delta ^{\lfloor \tfrac{r}{2}\rfloor }+O\left( \Delta ^{\tfrac{r+1}{3}}\right) \). We also prove that when r is even, \(A'_{r}\left( G\right) \le \Delta ^{\tfrac{r}{2}}+O\left( \Delta ^{\tfrac{r+1}{3}}\right) \), which is asymptotically optimal. In addition, we investigate how the r-acyclic edge chromatic number performs as the girth increases. It is proved in this paper that for every graph G with girth at least \(2r-1\), \(A'_r\left( G\right) \le \left( 9r-7\right) \Delta +10r-12\) holds. Our approach is based on the entropy compression method.     

Finding a minimal spanning hypertree of a weighted hypergraph

Journal of Combinatorial Optimization - A hypergraph has a complex structure, which is why some re- searchers seek to transform the hypergraph into a graph. In this paper, we present two...     

Adjacent vertex distinguishing total colorings of outerplanar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ″ _a (G). In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs.     

First-Fit colorings of graphs with no cycles of a prescribed even length

The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.     

Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five

An adjacent vertex distinguishing edge coloring of a graph \(G\) is a proper edge coloring of \(G\) such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of \(G\) is denoted by \(\chi ^{\prime }_{a}(G)\) . In this paper, we prove that if \(G\) is a planar graph with girth at least 5 and \(G\) is not a 5-cycle, then \(\chi ^{\prime }_{a}(G)\le \Delta +2\) , where \(\Delta \) is the maximum degree of \(G\) . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623–626, 2002).     

Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs

A graph G is said to be equitably k-colorable if the vertex set of G can be divided into k independent sets for which any two sets differ in size at most one. The equitable chromatic number of G, \(\chi _{=}(G)\), is the minimum k for which G is equitably k-colorable. The equitable chromatic threshold of G, \(\chi _{=}^{*}(G)\), is the minimum k for which G is equitably \(k'\)-colorable for all \(k'\ge k\). In this paper, the exact values of \(\chi _{=}^{*}(G\Box H)\) and \(\chi _{=}(G\Box H)\) are obtained when G is the square of a cycle or a path and H is a complete bipartite graph.     

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm \(SLS_{pc}\) (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701–1712, 2010]. For the average scheduling length of \(SLS_{pc}\) is 1 / m of GOW*, where \(m=\lfloor \varDelta _{max}\cdot p \rfloor \) is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and \(0<p<1\) is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm \(SLS_{pc}\) to that of GOW* are \(O(\varDelta _{max}/\overline{k})\), \(O(1/(\overline{k}\cdot \varDelta _{max}))\) and \(O(\varDelta _{max}/(\overline{k}\cdot m))\), respectively. Where \(\overline{k}\) (\(1<\overline{k}<\varDelta _{max}\)) is a constant called the SNR diversity of an instance G.     

Model-based and data-based planning systems

Decision models have been used in industry and government for over two decades. Increasingly they are being augmented and supplemented by data bases and data base support software that stores, retrieves, and aggregates data and establishes relationships between corresponding data elements in separate files. This has given rise to the development of systems that combine model-based and data-based functions in imaginative ways to provide more effective managerial support. In this article we examine this emerging concept and provide examples taken from a series of case studies.     

Personnel planning and information systems

Today the need for long-range planning is seen by most private and public organizations. Therefore growing attention to it is required of management in companies, in public services, in the armed services and in the school and university area. Some parts of the long-range planning problems have been widely discussed and practised. But there are some parts, which have received less attention in the business world. One of the relatively neglected areas, but one of special importance is long-range planning for personnel from the shop-floor up to top-management. This lack is remarkable, as one finds a lot of research and practical work on the use of other operations research planning systems, which cover for example queueing, inventory, production or investment problems. But in no field, is planning ahead more important than in personnel. Company growth and effectiveness depend on it. For unless a business organization has people with skill, imagination and a capacity for leadership, at the right time, its other plans may well be worthless.     

Modelling and controlling product manufacturing systems using bond-graphs and state equations: Continuous systems and discrete systems which can be represented by continuous models

This paper presents an approach to the modelling and control phases involved in a cooperative process of design and management of the manufacturing systems. Modelling the evolution of the production flow, in the different sections of the system, is based upon the use of the bondgraph methodology in order to reach the state formalism which constitutes one of the modern representations of automation. The class of the systems studied ranges from continuous systems to discrete systems, which can be represented by a continuous approach according to the level of approximation required. The first part of this paper is dedicated to the development of generic models associated with the various basic entities of the manufacturing systems. Then, the bondgraph model of any system is obtained by assembling generic models in relation to the implementation of the means of the studied system, thus guaranteeing a representation which is quite close to the engineering sketches. Finally, switching to the state equation is performed systematically with the easiness provided by this formalism while taking into account the causality principle. An application, involving most of the elementary models developed, concludes the paper.     

Restrictiveness and guidance in support systems

Restrictiveness and guidance have been proposed as methods for improving the performance of users of support systems. In many companies computerized support systems are used in demand forecasting enabling interventions based on management judgment to be applied to statistical forecasts. However, the resulting forecasts are often ‘sub-optimal’ because many judgmental adjustments are made when they are not required. An experiment was used to investigate whether restrictiveness or guidance in a support system leads to more effective use of judgment. Users received statistical forecasts of the demand for products that were subject to promotions. In the restrictiveness mode small judgmental adjustments to these forecasts were prohibited (research indicates that these waste effort and may damage accuracy). In the guidance mode users were advised to make adjustments in promotion periods, but not to adjust in non-promotion periods. A control group of users were not subject to restrictions and received no guidance. The results showed that neither restrictiveness nor guidance led to improvements in accuracy. While restrictiveness reduced unnecessary adjustments, it deterred desirable adjustments and also encouraged over-large adjustments so that accuracy was damaged. Guidance encouraged more desirable system use, but was often ignored. Surprisingly, users indicated it was less acceptable than restrictiveness.     

Information systems and managerial decision making

The role of an information system is to support managerial decision processes. Some of these processes can be completely specified in advance and, as long as the specification remains acceptable to management, resolution can be done automatically, within the framework of the information system. However, in other cases, managers are involved in all stages of the decision process, which cannot be completely specified in advance. The task of the information system in these cases is to provide information to the managers engaged in making the decisions. This paper considers these problems from the point of view of the information system designer and makes recommendations about design and implementation.     

Socio-political forecasting and management information systems

This paper is an attempt to place the forecasting of socio-political variables in the context of actual information needs of industrial companies. Initially discussion is of the effect of socio-political variables upon companies with a review of this significance for decision makers and decision takers. An attempt is then made to categorise existing forecasting techniques in the context of socio-political data whilst regard is paid to the possible effects of socio-political variables on companies. Discussion is then broadened to a consideration of current practice both in the UK and in the USA. Problems implicit in current practice are commented upon and the paper ends with the conclusion that socio-political forecasting is currently significant to many companies and that there is a major potential role for management scientists to play in the development and implementation of appropriate techniques.     

Performance measurement systems and time-based manufacturing

Today&apos;s production environment is often undermined by control mechanisms that were designed for another era. Specifically, most organizations control manufacturing wholly or in part using cost-based performance measurement systems. Depending upon the firm&apos;s objectives and key manufacturing task&lpar;s&rpar;, too much attention upon cost considerations can have devastating effects upon overall performance. This paper discusses this issue in the context of corporations that increasingly find themselves competing for business on the dimension of time. A case study is presented to illustrate how time-based companies can be adversely affected by an overemphasis upon cost.