Oriented graphs with prescribed -center and -median
Paths and stability number in digraphs.
Perfect matching preservers.
Permanents, Pfaffian orientations, and even directed circuits.
Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs.
Pólya's permanent problem.
Problems on fully irregular digraphs
Problems on stars in complete graphs.
Productive and inductive constructions of graphs
Products Of Digraphs And Their Competition Graphs
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
Properties of digraphs connected with some congruence relations
The paper extends the results given by M. Křížek and L. Somer, On a connection of number theory with graph theory, Czech. Math. J. 54 (129) (2004), 465–485 (see [5]). For each positive integer define a digraph whose set of vertices is the set and for which there is a directed edge from to if The properties of such digraphs are considered. The necessary and the sufficient condition for the symmetry of a digraph is proved. The formula for the number of fixed points of is established....
Quelques problèmes typiques concernant les graphes multiplicatifs
Quelques résultats sur «l' indice de transitivité» de certains tournois
Radial Digraphs
Radii and centers in iterated line digraphs
We show that the out-radius and the radius grow linearly, or "almost" linearly, in iterated line digraphs. Further, iterated line digraphs with a prescribed out-center, or a center, are constructed. It is shown that not every line digraph is admissible as an out-center of line digraph.
Rainbow Connectivity of Cacti and of Some Infinite Digraphs
An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair {u, v} ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds for the...
Random sampling of labeled tournaments.
Randomly Eulerian digraphs
Reachability relations and the structure of transitive digraphs.
Reconstructing a Graph from the Incidence Relation on its Edge Set