On fans in multigraphs

We introduce a unifying framework for studying edge‐coloring problems on multigraphs. This is defined in terms of a rooted directed multigraph , which is naturally associated to the set of fans based at a given vertex u in a multigraph G. We call the “Fan Digraph.” We show that fans in G based at u are in one‐to‐one correspondence with directed trails in starting at the root of . We state and prove a central theorem about the fan digraph, which embodies many edge‐coloring results and expresses them at a higher level of abstraction. Using this result, we derive short proofs of classical theorems. We conclude with a new, generalized version of Vizing's Adjacency Lemma for multigraphs, which is stronger than all those known to the author. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 301–318, 2006     

Improper choosability of graphs and maximum average degree

Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer g_k such that every planar graph of girth at least g_k is k‐improper 2‐choosable. He proved [9] that 6 ≤ g₁ ≤ 9; 5 ≤ g₂ ≤ 7; 5 ≤ g₃ ≤ 6; and ? k ≥ 4, g_k = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then . As a corollary, we deduce that g₁ ≤ 8 and g₂ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006     

An algorithm for the determination of graphs associated to fold maps between closed surfaces

The aim of this paper is to introduce a computational tool that checks theoretical conditions in order to determine whether a weighted graph, as a topological invariant of stable maps, can be associated to stable maps without cusps (ie, fold maps) from closed surfaces to the projective plan.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems

A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system $F\left(G\right)$ over a graph $G$ defines a set of transitions over $G$. A compatible Eulerian circuit of an Eulerian graph $G$ with a generalized transition system $F\left(G\right)$ is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by $F\left(G\right)$. In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively.     

An improved upper bound on the maximum degree of terminal-pairable complete graphs

A graph $G$ is terminal-pairable with respect to a demand (loopless) multigraph $D$ on the same vertex set as $G$, if there exist edge-disjoint paths joining the end vertices of every demand edge of $D$. In this short note, we improve the upper bound on the largest $\Delta \left(n\right)$ with the property that the complete graph on $n$ vertices is terminal-pairable with respect to any demand multigraph of maximum degree at most $\Delta \left(n\right)$. This disproves a conjecture originally stated by Csaba, Faudree, Gyárfás, Lehel and Schelp.     

Gap Functions and Error Bounds for Weak Generalized Ky Fan Inequalities

In this paper, we study a weak generalized Ky Fan inequality with cone constraints through image space analysis. First, we characterize the separation for the weak generalized Ky Fan inequality with cone constraints using the saddle points of generalized Lagrangian function. Then, we use regular weak separation functions to construct gap functions and regularized gap functions for the weak generalized Ky Fan inequality with cone constraints in a general way, and establish its error bounds in terms of these gap functions.     

Convergence Theorem for Variational Inequality in Hilbert Spaces with Applications

In this paper, we study variational inequality over the set of the common fixed points of a countable family of quasi-nonexpansive mappings. To tackle this problem, we propose an algorithm and use it to prove a strong convergence theorem under suitable conditions. As applications, we study variational inequality over the solution set of different nonlinear or linear problems, like minimization problems, split feasibility problems, convexly pseudoinverse problems, convex linear inverse problems, etc.