Concept
Mixed graph
Publications associées (44)
Coloring some classes of mixed graphs
We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring is a coloring such that for every edge , and for every arc , $c(x_{p})
2007Generalized connection graph method for synchronization in asymmetrical networks
We present a general framework for studying global complete synchronization in networks of dynamical systems with asymmetrical connections. We extend the connection graph stability method, originally developed for symmetrically coupled networks, to the gen ...
2006Some graph products and their expansion properties
Mohammad Amin Shokrollahi, Andrew Brown
We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non ...
2006Computing Vertex Connectivity: New Bounds from Old Techniques
The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time ...
2000On the number of small cuts in a graph
We prove that in an undirected graph there are at most O(n2) cuts of size strictly less than 3/2 of the size of the minimum cut. ...
1996