A mixed regular graph is a connected simple graph in which each vertex has both a fixed outdegree (the same indegree) and a fixed undirected degree. A mixed regular graphs is said to be optimal if ...there is not a mixed regular graph with the same parameters and bigger order.
We present a construction that provides mixed graphs of undirected degree q, directed degree q−12 and order 2q2, for q being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to 9q2−4q+34 the defect of these mixed graphs is (q−22)2−14.
In particular we obtain a known mixed Moore graph of order 18, undirected degree 3 and directed degree 1 called Bosák’s graph and a new mixed graph of order 50, undirected degree 5 and directed degree 2, which is proved to be optimal.
We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin 7 holds for all but finitely many ...graphs. We also use our method to prove special cases of a conjecture of Kahn 13. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.
In this note we construct a new infinite family of $(q-1)$-regular graphs of girth 8 and order $2q(q-1)^2$ for all prime powers $q\geq 16$, which are the smallest known so far whenever $q-1$ is not a ...prime power or a prime power plus one itself.
In the degree-diameter problem, the only extremal graph the existence of which is still in doubt is the Moore graph of order 3250, degree 57 and diameter 2. It has been known that such a graph cannot ...be vertex-transitive. Also, certain restrictions on the structure of the automorphism group of such a graph have been known in the case when the order of the group is even. In this paper we further investigate symmetries and structural properties of the missing Moore (57,
2)-graph(s) with the help of a combination of spectral, group-theoretic, combinatorial, and computational methods. One of the consequences is that the order of the automorphism group of such a graph is at most 375.
More on Moore graphs van Bon, John
Journal of combinatorial theory. Series A,
February 2013, 2013-02-00, Letnik:
120, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Let Δ be a tree such that each vertex has valency at least 3 and let A be a set of regular subgraphs of valency 2. In the early eighties A. Delgado and B. Stellmacher introduced the uniqueness and ...exchange conditions on the pair (Δ,A) and showed how they relate to generalized polygons. We modify the exchange condition and show how the modified version relates to Moore graphs. This is then used to give the isomorphism type of the amalgam of vertex stabilizers of two adjacent vertices in an s-arc transitive graph with trivial edge kernel and s⩾4.
Large-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented ...scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ A ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks. PUBLICATION ABSTRACT
PDF
