Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

路可扩图的一个充分条件

通过讨论图中任意一对不相邻顶点的度和,对路可扩图的充分条件进行研究,得到了如下结果：设图G的阶是n,如果G中任意一对不相邻顶点的度和至少为3/2n-1,则图G是路可扩的.并且说明了这里两不相邻顶点的度和的下界3/2n-1是最好可能的.     

A sufficient condition for boundedness of tolerance graphs

Golumbic, Monma, and Trotter showed that every tolerance graph for which no vertex neighborhood is contained in another vertex neighborhood is a bounded tolerance graph. We strengthen this result by weakening the neighborhood condition. In this way, more tolerance graphs can be recognized as bounded. Our argument relies on a variation of the concept of “assertive vertices”.     

A sufficient condition for bipartite graphs to be type one

The total chromatic number χ_T(G) of graph G is the least number of colors assigned to V(G) ∪ E(G) such that no adjacent or incident elements receive the same color. In this article, we give a sufficient condition for a bipartite graph G to have χ_T(G) = Δ(G) + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 133–137, 1998     

A sufficient condition on upper embeddability of graphs

In this paper we mainly prove that let G be a(k + 1)-edge-connected simple graph of order n with girth g.Then G is upper embeddable if for any independent set I(G) = {vi | 1 i k2 + 2},k = 0,1,2 and the lower bound is tight.     

A sharp upper bound on the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain an upper bound on the spectral radius of the adjacency matrix and characterize graphs for which the bound is attained.     

A property of weighted graphs without induced cycles of nonpositive weights

It has been conjectured [B. Xu, On signed cycle domination in graphs, Discrete Math. 309 (4) (2009) 1007–1012] that if there is a mapping from the edge set of a 2-connected graph G to {−1,1} such that for each induced subgraph, that is a cycle, the sum of all numbers assigned to its edges by this mapping is positive, then the number of all those edges of G to which 1 is assigned, is more than the number of all other edges of G. This conjecture follows from the main result of this note: If a mapping assigns integers as weights to the edges of a 2-connected graphGsuch that for each edge, its weight is not more than 1 and for each cycle which is an induced subgraph ofG, the sum of all weights of its edges is positive, then the sum of all weights of the edges ofGalso is positive. A simple corollary of this result is the following: If?is a mapping from the edge set of a 2-connected graphGto a set of real numbers such that for each cycleCofG, ∑_e∈E(C)?(e)>0, then∑_e∈E(G)?(e)also is positive.     

Performance safety enforcement in stochastic event graphs against boost and slow attacks

This paper studies a performance safety enforcing problem in stochastic event graphs, a subclass of stochastic Petri net models. We assume that an intruder can attack part of the transitions to increase/decrease their firing rate such that the performance of the system violates a given safety interval. The difficulty in solving this problem is that the capability of the intruder, i.e., the number of transitions that can be simultaneously attacked, is limited. The control aim is to find a protecting policy such that the performance of the protected plant is guaranteed to be in a given safety interval. We show that this problem can be formulated as a two-player game between the intruder and the operator of the plant. By using mixed integer linear programming technique, we develop a heuristic method to compute a protecting policy that is locally optimal.     

Quantitative analysis of continuous weighted marked graphs

This paper deals with the computation of the asymptotic firing rate vector and the stationary marking of continuous weighted marked graphs under infinite servers semantics. The continuous weighted marked graphs are a particular class of continuous Petri net where each place has exactly one input and one output transition. First, we give an explicit formula to compute the asymptotic firing rate vector of transitions using the structure of the given net. Then, under the assumption that there exists only one critical circuit in the strongly connected continuous neutral weighted marked graphs, an original approach to compute the vector of stationary marking is presented. Finally, an application to a flexible manufacturing system is given.     

The outflow ranking method for weighted directed graphs

A ranking method assigns to every weighted directed graph a (weak) ordering of the nodes. In this paper we axiomatize the ranking method that ranks the nodes according to their outflow using four independent axioms. Besides the well-known axioms of anonymity and positive responsiveness we introduce outflow monotonicity – meaning that in pairwise comparison between two nodes, a node is not doing worse in case its own outflow does not decrease and the other node’s outflow does not increase – and order preservation – meaning that adding two weighted digraphs such that the pairwise ranking between two nodes is the same in both weighted digraphs, then this is also their pairwise ranking in the ‘sum’ weighted digraph. The outflow ranking method generalizes the ranking by outdegree for directed graphs, and therefore also generalizes the ranking by Copeland score for tournaments.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Sequence of decisions on discrete event systems modeled by Petri nets with structural alternative configurations

The management of certain systems, such as manufacturing facilities, supply chains, or communication networks implies assessing the consequences of decisions, aimed for the most efficient operation. This kind of systems usually shows complex behaviors where subsystems present parallel evolutions and synchronizations. Furthermore, the existence of global objectives for the operation of the systems and the changes that experience the systems or their environment during their evolution imply a more or less strong dependence between decisions made at different time points of the life cycle. This paper addresses a complex problem that is scarcely present in the scientific literature: the sequences of decisions aimed for achieving several objectives simultaneously and with strong influence from one decision to the rest of them. In this case, the formal statement of the decision problem should take into account the whole decision sequence, making impractical the solving paradigm of “divide and conquer”. Only an integrated methodology may afford a realistic solution of such a type of decision problem. In this paper, an approach based on the formalism of the Petri nets is described, several considerations related to this problem are presented, a solving methodology based on the previous work of the authors, as well as a case-study to illustrate the main concepts.     

The new upper bounds on the spectral radius of weighted graphs

Let us consider weighted graphs, where the weights of the edges are positive definite matrices. The eigenvalues of a weighted graph are the eigenvalues of its adjacency matrix and the spectral radius of a weighted graph is also the spectral radius of its adjacency matrix. In this paper, we obtain two upper bounds for the spectral radius of weighted graphs and compare with a known upper bound. We also characterize graphs for which the upper bounds are attained.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

A new sufficient condition for hamiltonian graphs

We prove that a k-connected graph of order n, such that the number of neighbors of every independent set of k vertices is greater than (k(n – 1))/(k + 1) is hamiltonian.     

A sufficient condition for planar graphs to be acyclically 5‐choosable

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory