Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 68 for “"Degree sequence"”.

  1. The Degree Sequence Problem for 3-Hypergraphs

    Currently the degree sequence problem for 3-hypergraphs is still unsolved efficiently. This paper researches the 3-hypergraphic problem in terms of edge switching and exchanges in the sequence to implement Dewdney’s reduction. It proposes the idea of an irreducible decomposition and makes use of it …

    manitoba Repository record for The Degree Sequence Problem for 3-Hypergraphs (opens in a new tab)

  2. Sparse Trees with a Given Degree Sequence

    … under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph …

    gsu Repository record for Sparse Trees with a Given Degree Sequence (opens in a new tab)

  3. Sampling of Random Graphs with Prescribed Degree Sequence

    … when the number of connections of each node, the degree sequence, is prescribed. Among the improvements is a more stable method of calculating ensemble averages that allows much larger networks to be sampled. With the improved methods, results from hard constraint methods are compared with those …

    houston Repository record for Sampling of Random Graphs with Prescribed Degree Sequence (opens in a new tab)

  4. Graph Invariants of Trees with Given Degree Sequence

    … in Chemical Graph Theory, are defined on vertex degrees and distances between vertices. We explore generalizations of such graph indices and the corresponding extremal problems in trees. We will also briefly mention the applications of our results.

    gsu Repository record for Graph Invariants of Trees with Given Degree Sequence (opens in a new tab)

  5. Minimum independence number of graphs with specified degree sequences

    … on a graph's independence number in terms of the degree sequence of the graph. We present three functions of the degree sequence which are known lower bounds on independence number and compare them. We show that one of these functions, the residue, is often best possible. We determine explicitly …

    nebraska Repository record for Minimum independence number of graphs with specified degree sequences (opens in a new tab)

  6. Generating Random Graphs with Tunable Clustering Coefficient

    … the configuration model and that take triangle degree sequence (representing the number of triangles/corners at a node) and single-edge degree sequence (representing the number of single-edges/stubs at a node) as input and generate a random graph with a tunable clustering coefficient. We analyze …

    vt Repository record for Generating Random Graphs with Tunable Clustering Coefficient (opens in a new tab)

  7. Packings and realizations of degree sequences with specified substructures

    … areas in graph theory: graph packing and degree sequences. The question of packing degree sequences lies naturally in this intersection, asking when degree sequences have edge-disjoint realizations on the same vertex set. The most significant result in this area is Kundu’s k-Factor …

    nebraska Repository record for Packings and realizations of degree sequences with specified substructures (opens in a new tab)

  8. Graphs of Classroom Networks

    … method to create a simple graph from a graphical degree sequence. In this case, the degree sequence is a representation of the students in a classroom, and we use the number of peers with whom a student studied or collaborated to determine the degree of each. We expand upon the Havel-Hakimi …

    gsu Repository record for Graphs of Classroom Networks (opens in a new tab)

  9. Spectral Analysis of Randomly Generated Networks With Prescribed Degree Sequences

    … we generate random network samples with fixed degree sequences and then record properties of these samples. We begin with a real-world network, from which we extract a sample of at least one-hundred vertices through the use of snowball sampling. We record the degree sequence, D, of this sample …

    south-carolina Repository record for Spectral Analysis of Randomly Generated Networks With Prescribed Degree Sequences (opens in a new tab)

  10. Sampling uniform hypergraphs with given degrees

    … in which each edge has size k, each vertex has a degree specified by a degree sequence d, and all edges are unique. These are known as simple k-uniform hypergraphs with degree sequence d. We focus on algorithms for sampling these hypergraphs, particularly when the degree sequence is approximately …

    unsw Repository record for Sampling uniform hypergraphs with given degrees (opens in a new tab)

  11. Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs

    Any pair of graphs with the same degree sequence have the same number of edges, but they may not have the same subgraphs. In 1991 Erdős, Jacobson, and Lehel, introduced the concept of the `potential function' of a graph H: the least number of edges in a graph on n vertices for which some other …

    manitoba Repository record for Extremal properties of degree sequences: potential functions for subgraphs and forbidden subgraphs (opens in a new tab)

  12. Extremal Results and Algorithms for Degree Sequences of Graphs

    … 1) among all 2-multigraphs with the same degree sequence. In every parsimonious 2-multigraph, the subgraph of single edges consists of isolated stars and possibly one component that is a triangle. We prove the conjecture of Brualdi and Michael that for any fixed degree sequence, either …

    uiuc Repository record for Extremal Results and Algorithms for Degree Sequences of Graphs (opens in a new tab)

  13. Extremal problems in graphs

    In the first part of this thesis we will consider degree sequence results for graphs. An important result of Komlós [39] yields the asymptotically exact minimum degree threshold that ensures a graph \(G\) contains an \(H\)-tiling covering an \(x\)-proportion of the vertices of \(G\) (for any fixed …

    birmingham Download PDF for Extremal problems in graphs (opens in a new tab)

  14. On the Strongly Connected Components of Random Directed Graphs with Given Degree Sequences

    … a random directed graph with a well-behaved degree sequence asymptotically almost surely contains a giant strongly connected component. This is a new proof of a result by Cooper and Frieze in 2004. In addition, we predict the site percolation threshold for the presence of a giant strongly …

    waterloo Repository record for On the Strongly Connected Components of Random Directed Graphs with Given Degree Sequences (opens in a new tab)

  15. The Cover Time of Random Walks on Graph

    A simple random walk on a graph is a sequence of movements from one vertex to another where at each step an edge is chosen uniformly at random from the set of edges incident on the current vertex, and then transitioned to next vertex. Central to this thesis is the cover time of the walk, that is, …

    kings Repository record for The Cover Time of Random Walks on Graph (opens in a new tab) Download PDF for The Cover Time of Random Walks on Graph (opens in a new tab)

  16. Algorithms and Models for Tensors and Networks with Applications in Data Science

    … a very simple model where by design the expected degree sequence of a graph generated by the model is equal to a user-supplied degree sequence. We explore what happens both theoretically and numerically when simple changes are made to the model and when the model assumptions are violated. As well, …

    waterloo Repository record for Algorithms and Models for Tensors and Networks with Applications in Data Science (opens in a new tab)

  17. Cycles in graph theory and matroids

    … graph. A cycle is a graph such that the degree of each vertex is even. A graph G is Hamiltonian if it has a spanning circuit, and Hamiltonian-connected if for every pair of distinct vertices u, v ∈ V( G), G has a spanning (u, v)-path. A graph G is s-Hamiltonian if for any S ⊆ V (G) of …

    wvu Repository record for Cycles in graph theory and matroids (opens in a new tab)

  18. Graph centers, hypergraph degree sequences, and induced-saturation

    … the centralizing number of dense graphs. The degree sequence of a (hyper)graph is the list of the number of edges containing each vertex. A t-switch replaces t edges with t new edges while maintaining the same degree sequence. For graphs, it has been repeatedly shown that any realization of a …

    nebraska Repository record for Graph centers, hypergraph degree sequences, and induced-saturation (opens in a new tab)

  19. Graph diffusions and matrix functions: fast algorithms and localization results

    … stay localized on networks that have a skewed degree sequence related to the power-law degree distribution common to many real-world networks. Our results give the first theoretical explanation of a localization phenomenon that has long been observed in real-world networks. We prove our novel …

    purdue-thes Repository record for Graph diffusions and matrix functions: fast algorithms and localization results (opens in a new tab)

Page 1 of 4