اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn oriented graphs with minimal skew energy
164
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $S(G^sigma)$ be the skew-adjacency matrix of an oriented graph $G^sigma$. The skew energy of $G^sigma$ is defined as the sum of all singular values of its skew-adjacency matrix $S(G^sigma)$. In this paper, we first deduce an integral formula for the skew energy of an oriented graph. Then we determine all oriented graphs with minimal skew energy among all connected oriented graphs on $n$ vertices with $m (nle m < 2(n-2))$ arcs, which is an analogy to the conjecture for the energy of undirected graphs proposed by Caporossi {it et al.} [G. Caporossi, D. Cvetkovi$acute{c}$, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996.]
قيم البحث
اقرأ أيضاً
Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${rm inv}(D)$, is the minimum number of
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separator
s if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.
We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham and Wilson in the case of unoriented
graphs, and by Chung and Graham in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G the main result of Chung and Graham which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four-cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H
A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph is studied. For a particular family of gain graphs
with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph.
This paper has been withdrawn by the author.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
