1,720,991 research outputs found
Tactical decompositions of symmetric configurations
No full textSi introduce un nuovo metodo per descrivere decomposizioni tattiche di configurazioni simmetriche attraverso matrici (0,1) a blocchi, con somma costante sulle righe e sulle colonne, e i cui blocchi sono circolanti. Grazie a questo metodo si prova l’esistenza di una classe infinita di configurazioni simmetriche di tipo (2p2)p+s dove p è un numero primo ed s ≤ t un intero positivo tale che t – 1 è la più grande potenza prima con t2 – t + 1 ≤ p. In particolare si ottiene una nuova configurazione 98_1
Even orientations and pfaffian graphs
No full textWe give a characterization of pfaffian graphs in terms of even orientations, extending the characterization of near bipartite non-pfaffian graphs by Fischer and Little [4]. Our graph theoretical characterization is equivalent to the one proved by Little in [6] (cf. [8]) using linear algebra arguments
Extending perfect matchings to Hamiltonian cycles in line graphs
Full text linkA graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph G in order to guarantee that its line graph L(G) has the PMH-property. In particular, we prove that this happens when G is (i) a Hamiltonian graph with maximum degree at most 3, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper
One-factorizations of complete graphs with vertex-regular automorphism groups
No full textWe consider one-factorizations of K_2n possessing an automorphism group acting regularly (sharply transitively)on vertices. We present some upper bounds on the number of one-factors which are fixed by the group; further informationis obtained when equality holds in these bounds. The case where the group is dihedral is studied in some detail, with some non-existence statements in case the number of fixed one-factors is as large as possible. Constructions both for dihedral groups and for some classes of abelian groups are given
A Characterization of Graphs with Small Palette Index
Full text linkGiven an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3
- …
