Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

The (conditional) matching preclusion for burnt pancake graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial.     

Semistrong edge coloring of graphs

Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching M of a graph G is called semistrong if each edge of M has a vertex, which is of degree one in the induced subgraph G[M]. We strengthen earlier results by showing that for the subset graphs and for the Kneser graphs the sizes of the maxima of the strong and semistrong matchings are equal and so are the strong and semistrong chromatic indices. Similar properties are conjectured for the n‐dimensional cube. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 39–47, 2005     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Excluding Induced Subdivisions of the Bull and Related Graphs

For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph H, there is a function f_H: ?→? such that for every graph G∈Forb*(H), χ(G)≤f_H(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex‐disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012     

Strong clique trees,neighborhood trees,and strongly chordal graphs

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationships between chordal and strongly chordal graphs and the previously studied families of chordal bipartite graphs, clique graphs of chordal graphs (dually chordal graphs), and incidence graphs of biacyclic hypergraphs. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 151–160, 2000     

König–Egerváry Graphs are Non-Edmonds

König–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors ${{\bf{x}}\in\mathbb R^E}K?nig–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors x ? \mathbb R^E{{\bf{x}}\in\mathbb R^E} satisfying two families of constraints: ‘vertex saturation’ and ‘blossom’. Graphs for which the latter constraints are implied by the former are termed non-Edmonds. This note presents two proofs—one combinatorial, one algorithmic—of its title’s assertion. Neither proof relies on the characterization of non-Edmonds graphs due to de Carvalho et al. (J Combin Theory Ser B 92:319–324, 2004).     

Locating and paired-dominating sets in graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206]. A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. We consider paired-dominating sets which are also locating sets, that is distinct vertices of G are dominated by distinct subsets of the paired-dominating set. We consider three variations of sets which are paired-dominating and locating sets and investigate their properties.     

A note on mixed graphs and directed splitting off

We give counterexamples to two conjectures of Bill Jackson in Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs (Journal of Graph Theory 12 (3):429–436, 1988) concerning orientations of mixed graphs and splitting off in digraphs, and prove the first conjecture in the (di-) Eulerian case(s). Beside that we solve a degree constrained non-uniform directed augmentation problem for di-Eulerian mixed graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 213–221, 1998     

Fault tolerance of vertex pancyclicity in alternating group graphs

We study fault tolerance of vertex k pancyclicity of the alternating group graph AG_n. A graph G is vertex k pancyclic, if for every vertex p∈G, there is a cycle going through p of every length from k to |G|. Xue and Liu [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Proc. Lett. 109 (2009) 1197-1201] put the conjecture that AG_n is (2n-7)-fault-tolerant vertex pancyclic, which means that if the number of faults |F|?2n-7, then AG_n-F is still vertex pancyclic. Chang and Yang [J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] showed that for the shortest cycles the fault-tolerance of AG_n is much lower. They noted that with n-2 faults one can cut all 3-cycles going through a given vertex p (it is easy to observe that the same set of faults cuts all 4- and 5-cycles going through p). On the other hand they show that AG_n is n-3-fault tolerant vertex 3 pancyclic. In this paper we show that the cycles of length ?6 are much more fault-tolerant. More precisely, we show that AG_n is (2n-6)-fault-tolerant vertex 6 pancyclic. This bound is optimal, because every vertex p has 2n-4 neighbors.     

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

Cycle embedding in star graphs with conditional edge faults

Among the various interconnection networks, the star graph has been an attractive one. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ?2n-7 edge faults in which each vertex is incident with at least two healthy edges for n?4.     

Strong convergence of modified Mann iterations for a countable family of nonexpansive mappings

In this paper we propose a new modified Mann iteration for computing common fixed points of nonexpansive mappings in a Banach space. We give certain different control conditions for the modified Mann iteration. Then, we prove strong convergence theorems for a countable family of nonexpansive mappings in uniformly smooth Banach spaces. These results improve and extend results of Kim and Xu [T.H. Kim, H.K. Xu, Strong convergence of modified Mann iterations, Nonlinear Anal. 61 (2005) 51–60], Yao, et al. [Y. Yao, R. Chen and J. Yao, Strong convergence and certain control conditions for modified Mann iteration, Nonlinear Anal. 68 (2008) 1687–1693], Qin and Su [X. Qin, Y. Su, Approximation of a zero point of accretive operator in Banach spaces, J. Math. Anal. Appl. 329 (2007) 415–424], and many others.     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Forbidden subgraphs and the König–Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property  if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

Approximation of fixed points of nonexpansive mapping in Banach spaces

In this paper, some iterative schemes are given to approximate a fixed point of the nonexpansive non-self-mapping and nonexpansive self-mapping. Furthermore, the strong convergence of the scheme to a fixed point is shown in a Banach space with uniformly Gâteaux differentiable norm. The theorems extend and improve some corresponding results of Matsushita and Takahashi [S. Matsushita, W. Takahashi, Strong convergence theorems for nonexpansive nonself-mappings without boundary conditions, Nonlinear Anal. 68 (2008) 412–419], Chang et al. [S.S. Chang, H.W. Joseph Lee, C.K. Chan, On Reich’s strong convergence theorem for asymptotically nonexpansive mappings in Banach spaces, Nonlinear Anal. 66 (2007) 2364–2374], Chidume and Chidume [C.E. Chidume, C.O. Chidume, Iterative approximation of fixed points of nonexpansive mappings, J. Math. Anal. Appl. 318 (2006) 288–295] and Suzuki [T. Suzuki, A sufficient and necessary condition for Halpern-type strong convergence to fixed point of nonexpansive mappings, Proc. Amer. Math. Society 135 (1) (2007) 99–106].     

Crown reductions for the Minimum Weighted Vertex Cover problem

The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently in the unweighted case by Fellows et al. [Blow-Ups, Win/Win's and crown rules: some new directions in FPT, in: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG’03), Lecture notes in computer science, vol. 2880, 2003, pp. 1-12, Kernelization algorithms for the vertex cover problem: theory and experiments, in: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, Louisiana, January 2004, pp. 62-69]. We describe in detail a close relation of crown reductions to Nemhauser and Trotter reductions that are based on the linear programming relaxation of the problem. We introduce and study the so-called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints. It is described how crown decompositions and strong crown decompositions suitable for such problems can be computed in polynomial time. For weighted König-Egerváry graphs (G,w) we observe that the set of vertices belonging to all minimum vertex covers, and the set of vertices belonging to no minimum vertex covers, can be efficiently computed.Further, for some specific classes of graphs, simple algorithms for the MIN-VC problem with a constant approximation factor r<2 are provided. On the other hand, we conclude that for the regular graphs, or for the Hamiltonian connected graphs, the problem is as hard to approximate as for general graphs.It is demonstrated how the results about strong crown reductions can be used to achieve a linear size problem kernel for some related vertex cover problems.