Log in

Relevant bibliographies by topics / Random graphs / Journal articles

Journal articles on the topic 'Random graphs'

To see the other types of publications on this topic, follow the link: Random graphs.

Author: Grafiati

Published: 4 June 2021

Last updated: 29 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Random graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

FÜRER, MARTIN, and SHIVA PRASAD KASIVISWANATHAN. "Approximately Counting Embeddings into Random Graphs." Combinatorics, Probability and Computing 23, no. 6 (July 9, 2014): 1028–56. http://dx.doi.org/10.1017/s0963548314000339.

Full text

Abstract:

LetHbe a graph, and letCH(G) be the number of (subgraph isomorphic) copies ofHcontained in a graphG. We investigate the fundamental problem of estimatingCH(G). Previous results cover only a few specific instances of this general problem, for example the case whenHhas degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphsHand all graphsG, the algorithm is an unbiased estimator. Furthermore, for all graphsHhaving a decomposition where each of the bipartite graphs generated is small and almost all graphsG, the algorithm is a fully polynomial randomized approximation scheme.We show that the graph classes ofHfor which we obtain a fully polynomial randomized approximation scheme for almost allGincludes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.

APA, Harvard, Vancouver, ISO, and other styles

2

Kim, J. H., and V. H. Vu. "Sandwiching random graphs: universality between random graph models." Advances in Mathematics 188, no. 2 (November 2004): 444–69. http://dx.doi.org/10.1016/j.aim.2003.10.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Janson, Svante. "Quasi-random graphs and graph limits." European Journal of Combinatorics 32, no. 7 (October 2011): 1054–83. http://dx.doi.org/10.1016/j.ejc.2011.03.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Isufi, Elvin, Andreas Loukas, Andrea Simonetto, and Geert Leus. "Filtering Random Graph Processes Over Random Time-Varying Graphs." IEEE Transactions on Signal Processing 65, no. 16 (August 15, 2017): 4406–21. http://dx.doi.org/10.1109/tsp.2017.2706186.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

McDiarmid, C. "RANDOM GRAPHS." Bulletin of the London Mathematical Society 19, no. 3 (May 1987): 273. http://dx.doi.org/10.1112/blms/19.3.273a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ruciński, A. "Random graphs." ZOR Zeitschrift für Operations Research Methods and Models of Operations Research 33, no. 2 (March 1989): 145. http://dx.doi.org/10.1007/bf01415170.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Borbély, József, and András Sárközy. "Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)." Uniform distribution theory 14, no. 2 (December 1, 2019): 103–26. http://dx.doi.org/10.2478/udt-2019-0017.

Full text

Abstract:

AbstractIn the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and strongly pseudo-random graphs, respectively.)

APA, Harvard, Vancouver, ISO, and other styles

8

Gao, Yong. "Treewidth of Erdős–Rényi random graphs, random intersection graphs, and scale-free random graphs." Discrete Applied Mathematics 160, no. 4-5 (March 2012): 566–78. http://dx.doi.org/10.1016/j.dam.2011.10.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

KOHAYAKAWA, YOSHIHARU, GUILHERME OLIVEIRA MOTA, and MATHIAS SCHACHT. "Monochromatic trees in random graphs." Mathematical Proceedings of the Cambridge Philosophical Society 166, no. 1 (January 16, 2018): 191–208. http://dx.doi.org/10.1017/s0305004117000846.

Full text

Abstract:

AbstractBal and DeBiasio [Partitioning random graphs into monochromatic components, Electron. J. Combin.24(2017), Paper 1.18] put forward a conjecture concerning the threshold for the following Ramsey-type property for graphsG: everyk-colouring of the edge set ofGyieldskpairwise vertex disjoint monochromatic trees that partition the whole vertex set ofG. We determine the threshold for this property for two colours.

APA, Harvard, Vancouver, ISO, and other styles

10

Ferber, Asaf, Kyle Luh, and Oanh Nguyen. "Embedding large graphs into a random graph." Bulletin of the London Mathematical Society 49, no. 5 (July 10, 2017): 784–97. http://dx.doi.org/10.1112/blms.12066.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Diaconis, Persi, Susan Holmes, and Svante Janson. "Threshold Graph Limits and Random Threshold Graphs." Internet Mathematics 5, no. 3 (January 2008): 267–320. http://dx.doi.org/10.1080/15427951.2008.10129166.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Whittle, P. "Random fields on random graphs." Advances in Applied Probability 24, no. 2 (June 1992): 455–73. http://dx.doi.org/10.2307/1427700.

Full text

Abstract:

The distribution (1) used previously by the author to represent polymerisation of several types of unit also prescribes quite general statistics for a random field on a random graph. One has the integral expression (3) for its partition function, but the multiple complex form of the integral makes the nature of the expected saddlepoint evaluation in the thermodynamic limit unclear. It is shown in Section 4 that such an evaluation at a real positive saddlepoint holds, and subsidiary conditions narrowing down the choice of saddlepoint are deduced in Section 6. The analysis simplifies greatly in what is termed the semi-coupled case; see Sections 3, 5 and 7. In Section 8 the analysis is applied to an Ising model on a random graph of fixed degreer+ 1. The Curie point of this model is found to agree with that deduced by Spitzer for an Ising model on an r-branching tree. This agreement strengthens the conclusion of ‘locally tree-like' behaviour of the graph, seen as an important property in a number of contexts.

APA, Harvard, Vancouver, ISO, and other styles

13

Bender, E. A., and N. C. Wormald. "Random trees in random graphs." Proceedings of the American Mathematical Society 103, no. 1 (January 1, 1988): 314. http://dx.doi.org/10.1090/s0002-9939-1988-0938689-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Whittle, P. "Random fields on random graphs." Advances in Applied Probability 24, no. 02 (June 1992): 455–73. http://dx.doi.org/10.1017/s0001867800047601.

Full text

Abstract:

The distribution (1) used previously by the author to represent polymerisation of several types of unit also prescribes quite general statistics for a random field on a random graph. One has the integral expression (3) for its partition function, but the multiple complex form of the integral makes the nature of the expected saddlepoint evaluation in the thermodynamic limit unclear. It is shown in Section 4 that such an evaluation at a real positive saddlepoint holds, and subsidiary conditions narrowing down the choice of saddlepoint are deduced in Section 6. The analysis simplifies greatly in what is termed the semi-coupled case; see Sections 3, 5 and 7. In Section 8 the analysis is applied to an Ising model on a random graph of fixed degree r + 1. The Curie point of this model is found to agree with that deduced by Spitzer for an Ising model on an r-branching tree. This agreement strengthens the conclusion of ‘locally tree-like' behaviour of the graph, seen as an important property in a number of contexts.

APA, Harvard, Vancouver, ISO, and other styles

15

?uczak, Tomasz. "Random trees and random graphs." Random Structures and Algorithms 13, no. 3-4 (October 1998): 485–500. http://dx.doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<485::aid-rsa16>3.0.co;2-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Capitaine, M., S. Coste, F. Gabriel, P. Maillard, and C. Mailler. "Random matrices and random graphs." ESAIM: Proceedings and Surveys 74 (November 2023): 137–57. http://dx.doi.org/10.1051/proc/202374137.

Full text

Abstract:

We collect recent results on random matrices and random graphs. The topics covered are: fluctuations of the empirical measure of random matrices, finite-size effects of algorithms involving random matrices, characteristic polynomial of sparse matrices and Voronoi tesselations of split trees.

APA, Harvard, Vancouver, ISO, and other styles

17

Larrión, F., M. A. Pizaña, and R. Villarroel-Flores. "Random Graphs, Retractions and Clique Graphs." Electronic Notes in Discrete Mathematics 30 (February 2008): 285–90. http://dx.doi.org/10.1016/j.endm.2008.01.049.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Ruciński, Andrzej, and Andrew Vince. "Strongly balanced graphs and random graphs." Journal of Graph Theory 10, no. 2 (1986): 251–64. http://dx.doi.org/10.1002/jgt.3190100214.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Mori, Tamas F., and Sandor Rokob. "Random cherry graphs." Publicationes Mathematicae Debrecen 95, no. 1-2 (July 1, 2019): 93–114. http://dx.doi.org/10.5486/pmd.2019.8384.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Cannings, Chris. "Random Geometric Graphs." Journal of the Royal Statistical Society: Series A (Statistics in Society) 168, no. 3 (July 2005): 636. http://dx.doi.org/10.1111/j.1467-985x.2005.00368_12.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Bachas, C., C. de Calan, and P. M. S. Petropoulos. "Quenched random graphs." Journal of Physics A: Mathematical and General 27, no. 18 (September 21, 1994): 6121–27. http://dx.doi.org/10.1088/0305-4470/27/18/020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Blasiak, Jonah, and Rick Durrett. "Random Oxford graphs." Stochastic Processes and their Applications 115, no. 8 (August 2005): 1257–78. http://dx.doi.org/10.1016/j.spa.2005.03.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Bollobás, B., P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. "Random induced graphs." Discrete Mathematics 248, no. 1-3 (April 2002): 249–54. http://dx.doi.org/10.1016/s0012-365x(01)00345-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Scheinerman, E. R. "Random interval graphs." Combinatorica 8, no. 4 (December 1988): 357–71. http://dx.doi.org/10.1007/bf02189092.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Krivelevich, Michael, and Benny Sudakov. "Coloring random graphs." Information Processing Letters 67, no. 2 (July 1998): 71–74. http://dx.doi.org/10.1016/s0020-0190(98)00092-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Chung, F. R. K., R. L. Graham, and R. M. Wilson. "Quasi-random graphs." Proceedings of the National Academy of Sciences 85, no. 4 (February 1, 1988): 969–70. http://dx.doi.org/10.1073/pnas.85.4.969.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

McDiarmid, Colin, Angelika Steger, and Dominic J. A. Welsh. "Random planar graphs." Journal of Combinatorial Theory, Series B 93, no. 2 (March 2005): 187–205. http://dx.doi.org/10.1016/j.jctb.2004.09.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Chung, F. R. K., R. L. Graham, and R. M. Wilson. "Quasi-random graphs." Combinatorica 9, no. 4 (December 1989): 345–62. http://dx.doi.org/10.1007/bf02125347.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

McDiarmid, Colin, and Nikola Yolov. "Random perfect graphs." Random Structures & Algorithms 54, no. 1 (March 5, 2018): 148–86. http://dx.doi.org/10.1002/rsa.20770.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Pippenger, Nicholas. "Random interval graphs." Random Structures and Algorithms 12, no. 4 (July 1998): 361–80. http://dx.doi.org/10.1002/(sici)1098-2418(199807)12:4<361::aid-rsa4>3.0.co;2-r.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Kim, Jeong Han, Benny Sudakov, and Van H. Vu. "On the asymmetry of random regular graphs and random graphs." Random Structures and Algorithms 21, no. 3-4 (October 2002): 216–24. http://dx.doi.org/10.1002/rsa.10054.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Anbo, Yuki. "Random graphs with a random bijection." Tsukuba Journal of Mathematics 35, no. 1 (June 2011): 143–51. http://dx.doi.org/10.21099/tkbjm/1311081455.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Leri, Marina, and Yury Pavlov. "Random Graphs' Robustness in Random Environment." Austrian Journal of Statistics 46, no. 3-4 (April 12, 2017): 89–98. http://dx.doi.org/10.17713/ajs.v46i3-4.674.

Full text

Abstract:

We consider configuration graphs the vertex degrees of which are independent and follow the power-law distribution. Random graphs dynamics takes place in a random environment with the parameter of vertex degree distribution following uniform distributions on finite fixed intervals. As the number of vertices tends to infinity the limit distributions of the maximum vertex degree and the number of vertices with a given degree were obtained. By computer simulations we study the robustness of those graphs from the viewpoints of link saving and node survival in the two cases of the destruction process: the ``targeted attack'' and the ``random breakdown''. We obtained and compared the results under the conditions that the vertex degree distribution was averaged with respect to the distribution of the power-law parameter or that the values of the parameter were drawn from the uniform distribution separately for each vertex.

APA, Harvard, Vancouver, ISO, and other styles

34

Hildebrand, Martin. "Random walks on random simple graphs." Random Structures and Algorithms 8, no. 4 (July 1996): 301–18. http://dx.doi.org/10.1002/(sici)1098-2418(199607)8:4<301::aid-rsa2>3.0.co;2-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Wu, Jun, Mauricio Barahona, Yue-jin Tan, and Hong-zhong Deng. "Robustness of random graphs based on graph spectra." Chaos: An Interdisciplinary Journal of Nonlinear Science 22, no. 4 (December 2012): 043101. http://dx.doi.org/10.1063/1.4754875.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Aiello, William, Fan Chung, and Linyuan Lu. "A Random Graph Model for Power Law Graphs." Experimental Mathematics 10, no. 1 (January 2001): 53–66. http://dx.doi.org/10.1080/10586458.2001.10504428.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Komjáthy, Júlia, and Bas Lodewijks. "Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs." Stochastic Processes and their Applications 130, no. 3 (March 2020): 1309–67. http://dx.doi.org/10.1016/j.spa.2019.04.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Asplund, John, Thao Do, Arran Hamm, László Székely, Libby Taylor, and Zhiyu Wang. "k-planar crossing number of random graphs and random regular graphs." Discrete Applied Mathematics 247 (October 2018): 419–22. http://dx.doi.org/10.1016/j.dam.2018.04.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Gray, Caitlin, Lewis Mitchell, and Matthew Roughan. "Generating connected random graphs." Journal of Complex Networks 7, no. 6 (March 20, 2019): 896–912. http://dx.doi.org/10.1093/comnet/cnz011.

Full text

Abstract:

Abstract Sampling random graphs is essential in many applications, and often algorithms use Markov chain Monte Carlo methods to sample uniformly from the space of graphs. However, often there is a need to sample graphs with some property that we are unable, or it is too inefficient, to sample using standard approaches. In this article, we are interested in sampling graphs from a conditional ensemble of the underlying graph model. We present an algorithm to generate samples from an ensemble of connected random graphs using a Metropolis–Hastings framework. The algorithm extends to a general framework for sampling from a known distribution of graphs, conditioned on a desired property. We demonstrate the method to generate connected spatially embedded random graphs, specifically the well-known Waxman network, and illustrate the convergence and practicalities of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

40

Bollobás, Béla, Graham Brightwell, and Jaroslav Nešetřil. "Random graphs and covering graphs of posets." Order 3, no. 3 (September 1986): 245–55. http://dx.doi.org/10.1007/bf00400288.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Bochi, Jairo, Godofredo Iommi, and Mario Ponce. "Perfect matchings in inhomogeneous random bipartite graphs in random environment." Cubo (Temuco) 24, no. 2 (August 2022): 263–72. http://dx.doi.org/10.56754/0719-0646.2402.0263.

Full text

Abstract:

In this note we study inhomogeneous random bipartite graphs in random environment. These graphs can be thought of as an extension of the classical Erdős-Rényi random bipartite graphs in a random environment. We show that the expected number of perfect matchings obeys a precise asymptotic.

APA, Harvard, Vancouver, ISO, and other styles

42

DÍAZ, JOSEP, MATHEW D. PENROSE, JORDI PETIT, and MARÍA SERNA. "Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs." Combinatorics, Probability and Computing 9, no. 6 (November 2000): 489–511. http://dx.doi.org/10.1017/s0963548300004454.

Full text

Abstract:

This work deals with convergence theorems and bounds on the cost of several layout measures for lattice graphs, random lattice graphs and sparse random geometric graphs. Specifically, we consider the following problems: Minimum Linear Arrangement, Cutwidth, Sum Cut, Vertex Separation, Edge Bisection and Vertex Bisection. For full square lattices, we give optimal layouts for the problems still open. For arbitrary lattice graphs, we present best possible bounds disregarding a constant factor. We apply percolation theory to the study of lattice graphs in a probabilistic setting. In particular, we deal with the subcritical regime that this class of graphs exhibits and characterize the behaviour of several layout measures in this space of probability. We extend the results on random lattice graphs to random geometric graphs, which are graphs whose nodes are spread at random in the unit square and whose edges connect pairs of points which are within a given distance. We also characterize the behaviour of several layout measures on random geometric graphs in their subcritical regime. Our main results are convergence theorems that can be viewed as an analogue of the Beardwood, Halton and Hammersley theorem for the Euclidean TSP on random points in the unit square.

APA, Harvard, Vancouver, ISO, and other styles

43

Gishboliner, Lior, Michael Krivelevich, and Gal Kronenberg. "On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments." Random Structures & Algorithms 52, no. 4 (December 29, 2017): 545–59. http://dx.doi.org/10.1002/rsa.20751.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Bóna, Miklós. "Review of Random graphs." ACM SIGACT News 40, no. 3 (September 25, 2009): 46–48. http://dx.doi.org/10.1145/1620491.1620499.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

House, T. "Heterogeneous clustered random graphs." EPL (Europhysics Letters) 105, no. 6 (March 1, 2014): 68006. http://dx.doi.org/10.1209/0295-5075/105/68006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Fremlin, D. H., and M. Talagrand. "Subgraphs of random graphs." Transactions of the American Mathematical Society 291, no. 2 (February 1, 1985): 551. http://dx.doi.org/10.1090/s0002-9947-1985-0800252-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Dellamonica,, Domingos, Yoshiharu Kohayakawa, Vojtěch Rödl, and Andrzej Ruciński. "Universality of Random Graphs." SIAM Journal on Discrete Mathematics 26, no. 1 (January 2012): 353–74. http://dx.doi.org/10.1137/10079882x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Mourrat, Jean-Christophe, and Daniel Valesin. "Spatial Gibbs random graphs." Annals of Applied Probability 28, no. 2 (April 2018): 751–89. http://dx.doi.org/10.1214/17-aap1316.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Biró, Csaba, and Udayan B. Darji. "Generating Infinite Random Graphs." Proceedings of the Edinburgh Mathematical Society 61, no. 3 (May 22, 2018): 847–68. http://dx.doi.org/10.1017/s0013091517000487.

Full text

Abstract:

AbstractWe define a growing model of random graphs. Given a sequence of non-negative integers {dn}n=0∞ with the property that di≤i, we construct a random graph on countably infinitely many vertices v0, v1… by the following process: vertex vi is connected to a subset of {v0, …, vi−1} of cardinality di chosen uniformly at random. We study the resulting probability space. In particular, we give a new characterization of random graphs, and we also give probabilistic methods for constructing infinite random trees.

APA, Harvard, Vancouver, ISO, and other styles

50

Cameron, Peter J. "Random strongly regular graphs?" Electronic Notes in Discrete Mathematics 10 (November 2001): 54–63. http://dx.doi.org/10.1016/s1571-0653(04)00358-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!