Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

Upper Bounds to the Number of Vertices in a k-Critically n-Connected Graph

 Let k≤n be positive integers. A finite, simple, undirected graph is called k-critically n-connected, or, briefly, an (n,k)-graph, if it is noncomplete and n-connected and the removal of any set X of at most k vertices results in a graph which is not (n−|X|+1)-connected. We present some new results on the number of vertices of an (n,k)-graph, depending on new estimations of the transversal number of a uniform hypergraph with a large independent edge set. Received: April 14, 2000 Final version received: May 8, 2001     

A note on balance vertices in trees

The notion of balanced bipartitions of the vertices in a tree T was introduced and studied by Reid (Networks 34 (1999) 264). Reid proved that the set of balance vertices of a tree T consists of a single vertex or two adjacent vertices. In this note, we give a simple proof of that result.     

Tangent cones and Dini derivatives

We prove a property of the Bouligand tangent cone to the epigraph (or to the graph) of a locally Lipschitz function. It is also shown how this result can be used in determining Dini sequences. Finally, some relationships between such a cone and Dini derivatives are provided.     

Further generalization of the Dubovicki-Milutin theorem

Combining the results of Walczak (Ref. 1) and Lasiecka (Refs. 2 and 3), we extend the well-known Dubovicki-Milutin theorem in two directions: (i) We allow for treatment of several equality constraints in optimization problems; and (ii) We assume less regularity of optimization problems by requiring the existence of external cones instead of tangent cones. An example of an optimization problem is also considered.     

Several parameters of generalized Mycielskians

The generalized Mycielskians (also known as cones over graphs) are the natural generalization of the Mycielski graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer m?0, one can transform G into a new graph μ_m(G), the generalized Mycielskian of G. This paper investigates circular clique number, total domination number, open packing number, fractional open packing number, vertex cover number, determinant, spectrum, and biclique partition number of μ_m(G).     

A note on acyclic domination number in graphs of diameter two

A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γ_a(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if δ(G) is the minimum degree of G, is γ_a(G)?δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive k, there is a graph G with diameter two such that γ_a(G)-δ(G)?k.     

广义凸集的支撑函数

本文讨论了笔者在[1]中提出的伪凸集,拟凸集的支撑函数与障碍锥的性质,并通过这些性质得出了二个闭性准则。     

Codiameters of 3‐connected 3‐domination critical graphs

A graph G is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a 3‐connected 3‐domination critical graph of order n. In this paper, we show that there is a path of length at least n?2 between any two distinct vertices in G and the lower bound is sharp. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 76–85, 2002