| Popis: |
Naj bosta n in k naravni števili in n≥k. To diplomsko delo predstavlja nov razred grafov H(n,k), ki vsebuje hiperkocke ter Johnsonove in Kneserjeve grafe kot njegove podgrafe. V prvem poglavju so povzeti osnovni pojmi iz teorije grafov, v drugem delu pa bodo predstavljeni nekateri rezultati vezani na družino H(n,k). Na primer, H(n,k) ima maksimalno povezanost (n nad k), H(n,k) je Hamiltonov, če je k liho število ter je sestavljen iz dveh izomorfnih povezanih komponent, če je k sodo število. Let n and k be positive integers and n≥k. This Graduation Thesis represents a new class of graphs H(n,k), which contains hypercubes, Johnson and Kneser graphs as its subgraphs. The first part summarizes the basic concepts of graph theory, while the second part will present some of the results linked to the family H(n,k). For example, H(n,k) has the maximum connectivity (n choose k), H(n,k) is hamiltonian if k is an odd number, and it consists of two isomorphic connected components if k is even. |
