We give a sufficient and necessary condition for a finite graph to admit a tight and substantial polygonal map into the n-dimensional Euclidean space. As a consequence, we determine the curvature ...dimension for 2-connected graphs explicitly from their topological structure.
Back to Classes Nešetřil, Jaroslav; de Mendez, Patrice Ossona
Sparsity
Book Chapter
In this chapter we summarize the results on sparsity of classes with all their characterizations. The multiplicity of the equivalent characterizations that can be given for the nowhere ...dense–somewhere dense dichotomy is mainly a consequence of several related aspects:
Kinkar Ch. Das, Muhuo Liu.
Obsahuje seznam literatury
n this paper, the upper and lower bounds for the quotient of spectral radius (Laplacian spectral radius, signless Laplacian spectral radius) and ...the clique number together with the corresponding extremal graphs in the class of connected graphs with n vertices and clique number ω(2 ≤ ω ≤ n) are determined. As a consequence of our results, two conjectures given in Aouchiche (2006) and Hansen (2010) are proved.
Lower and upper bounds are obtained for the clique number $\omega (G)$ and the independence number $\alpha (G)$, in terms of the eigenvalues of the signless Laplacian matrix of a graph $G$.
We exploit the combinatorial structure of conceptual graphs in order to obtain better execution times when computing projection, which is a core generalisation-specialisation relation over conceptual ...graphs. We show how the problem of finding this relation can be translated into the Maximum Clique problem. Consequently, approximation techniques developed for the Maximum Clique problem can be used to compute projection in conceptual graphs. We show that there are “simple queries” which can be answered quickly, thus providing efficient reasoning support in a knowledge management environment based on conceptual graphs.
Mojgan Afkhami, Kazem Khashyarmanesh, Zohreh Rajabi.
Obsahuje bibliografii
Let R be a commutative ring. The annihilator graph of R, denoted by AG(R), is the undirected graph with all nonzero ...zero-divisors of R as vertex set, and two distinct vertices x and y are adjacent if and only if ann(xy) \neqann R(x)\cup annR(y), where for z \in R, annR(z) = {r \in R: rz = 0}. In this paper, we characterize all finite commutative rings R with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings R whose annihilator graphs have clique number 1, 2 or 3. Also, we investigate some properties of the annihilator graph under the extension of R to polynomial rings and rings of fractions. For instance, we show that the graphs AG(R) and AG(T(R)) are isomorphic, where T(R) is the total quotient ring of R. Moreover, we investigate some properties of the annihilator graph of the ring of integers modulo n, where n>1.
In wireless networks, to avoid collisions of simultaneous transmissions over the same channel, adjacent nodes are assigned distinct channels, and the least number of channels used in an assignment is ...called the chromatic number. The determination of the chromatic number is NP-hard. In this paper, we introduce an analytic tool called maximum scan statistics. For a finite point set
V
and a convex compact set
C
, the maximum scan statistic of
V
with respect to the scanning set
C
is the largest number of points in
V
covered by a copy
C
. Based on the study of asymptotic maximum scan statistics, we obtain the asymptotics of the maximum degree and the clique number of homogeneous wireless networks. The results imply that the chromatic number is almost surely at most four times the clique number. We further prove that the approximation ratios of some vertex-ordering-based First-Fit channel assignment algorithms are almost surely bounded by 2. In the analysis, we also learn that the chromatic number is almost surely at most twice the clique number.
PDF
