Nagrinėjami atsitiktiniai sankirtų grafai G(n,m,p)jų viršūnių laipsnių skirstinius. Įrodyta, kad grafo viršūnės laipsnis turi Binominį pasiskirstymą. Rasta išraiška tikimybės p, kad dvi grafo viršūnės renkasi bendrą objektą. / Random intersection graphs audits vertex degree distributions are viewed. Its proved, vertex degree has Binomial distribution. Probability p that two vertex of graph chooses common object is find.

Let G=(V,E) be a graph with vertex set V and edge set E. A vertex v∈V ve-dominates every edge incident to it as well as every edge adjacent to these incident edges. The vertex–edge degree of a vertex v is the number of edges ve-dominated by v. Similarly, an edge e=uv ev-dominates the two vertices u and v incident to it, as well as every vertex adjacent to u or v. The edge–vertex degree of an edge e is the number of vertices ev-dominated by edge e. In this paper we introduce these types of degrees and study their properties.

We say a graph is locally P if the induced graph on the neighbourhood of every vertex has the property P. Specically, a graph is locally traceable (LT) or locally hamiltonian (LH) if the induced graph on the neighbourhood of every vertex is traceable or hamiltonian, respectively. A locally locally hamiltonian (L2H) graph is a graph in which the graph induced by the neighbourhood of each vertex is an LH graph. This concept is generalized to an arbitrary degree of nesting, to make it possible to work with LkH graphs. This thesis focuses on the global cycle properties of LT, LH and LkH graphs. Methods are developed to construct and combine such graphs to create others with desired properties. It is shown that with the exception of three graphs, LT graphs with maximum degree no greater than 5 are fully cycle extendable (and hence hamiltonian), but the Hamilton cycle problem for LT graphs with maximum degree 6 is NP-complete. Furthermore, the smallest nontraceable LT graph has order 10, and the smallest value of the maximum degree for which LT graphs can be nontraceable is 6. It is also shown that LH graphs with maximum degree 6 are fully cycle extendable, and that there exist nonhamiltonian LH graphs with maximum degree 9 or less for all orders greater than 10. The Hamilton cycle problem is shown to be NP-complete for LH graphs with maximum degree 9. The construction of r-regular nonhamiltonian graphs is demonstrated, and it is shown that the number of vertices in a longest path in an LH graph can contain a vanishing fraction of the vertices of the graph. NP-completeness of the Hamilton cycle problem for LkH graphs for higher values of k is also investigated. / Mathematical Sciences / D. Phil. (Mathematics)

No description available.