To see the other types of publications on this topic, follow the link: Graphe n-partie.
Journal articles on the topic 'Graphe n-partie'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Graphe n-partie.'
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
Laomala, Janejira, Keaitsuda Maneeruk Nakprasit, Kittikorn Nakprasit, and Watcharintorn Ruksasakchai. "The Strong Equitable Vertex 1-Arboricity of Complete Bipartite Graphs and Balanced Complete k-Partite Graphs." Symmetry 14, no. 2 (January 31, 2022): 287. http://dx.doi.org/10.3390/sym14020287.
Full textAbstract:
An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color classes differ by at most one. An equitable (q,r)-tree-coloring of a graph G is an equitable q-coloring of G such that the subgraph induced by each color class is a forest of maximum degree at most r. Let the strong equitable vertex r-arboricity of a graph G, denoted by var≡(G), be the minimum p such that G has an equitable (q,r)-tree-coloring for every q≥p. The values of va1≡(Kn,n) were investigated by Tao and Lin and Wu, Zhang, and Li where exact values of va1≡(Kn,n) were found in some special cases. In this paper, we extend their results by giving the exact values of va1≡(Kn,n) for all cases. In the process, we introduce a new function related to an equitable coloring and obtain a more general result by determining the exact value of each va1≡(Km,n) and va1≡(G) where G is a balanced complete k-partite graph Kn,…,n. Both complete bipartite graphs Km,n and balanced complete k-partite graphs Kn,…,n are symmetry in several aspects and also studied broadly. For the other aspect of symmetry, by the definition of equitable k-coloring of graphs, in a specific case that the number of colors divides the number of vertices of graph, we can say that the graph is a balanced k-partite graph.
2
YUSTER, RAPHAEL. "Independent Transversals and Independent Coverings in Sparse Partite Graphs." Combinatorics, Probability and Computing 6, no. 1 (March 1997): 115–25. http://dx.doi.org/10.1017/s0963548396002763.
Full textAbstract:
An [n, k, r]-partite graph is a graph whose vertex set, V, can be partitioned into n pairwise-disjoint independent sets, V1, …, Vn, each containing exactly k vertices, and the subgraph induced by Vi ∪ Vj contains exactly r independent edges, for 1 [les ] i < j [les ] n. An independent transversal in an [n, k, r]-partite graph is an independent set, T, consisting of n vertices, one from each Vi. An independent covering is a set of k pairwise-disjoint independent transversals. Let t(k, r) denote the maximal n for which every [n, k, r]-partite graph contains an independent transversal. Let c(k, r) be the maximal n for which every [n, k, r]-partite graph contains an independent covering. We give upper and lower bounds for these parameters. Furthermore, our bounds are constructive. These results improve and generalize previous results of Erdo″s, Gyárfás and Łuczak [5], for the case of graphs.
3
Poojary, Raksha, Arathi Bhat K, Manjunatha Prasad Karantha, S. Arumugam, and Ivan Gutman. "Characterizing Graphs with Nullity n-4." match Communications in Mathematical and in Computer Chemistry 89, no. 3 (2023): 631–42. http://dx.doi.org/10.46793/match.89-3.631p.
Full textAbstract:
The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of G. A unified approach is presented for the characterization of graphs of order n with η(G) = n−4. All known results on trees, unicyclic graphs, bicyclic graphs, graphs with minimum degree 1, and r-partite graphs, for which η(G) = n−4 are shown to be corollaries of a theorem of Chang, Huang and Yeh that characterizes all graphs with nullity n − 4.
4
Pushpam, P. Roushini Leely, and D. Yokesh. "Differentials in certain classes of graphs." Tamkang Journal of Mathematics 41, no. 2 (June 30, 2010): 129–38. http://dx.doi.org/10.5556/j.tkjm.41.2010.664.
Full textAbstract:
Let $X subset V$ be a set of vertices in a graph $G = (V, E)$. The boundary $B(X)$ of $X$ is defined to be the set of vertices in $V-X$ dominated by vertices in $X$, that is, $B(X) = (V-X) cap N(X)$. The differential $ partial(X)$ of $X$ equals the value $ partial(X) = |B(X)| - |X|$. The differential of a graph $G$ is defined as $ partial(G) = max { partial(X) | X subset V }$. It is easy to see that for any graph $G$ having vertices of maximum degree $ Delta(G)$, $ partial(G) geq Delta (G) -1$. In this paper we characterize the classes of unicyclic graphs, split graphs, grid graphs, $k$-regular graphs, for $k leq 4$, and bipartite graphs for which $ partial(G) = Delta(G)-1$. We also determine the value of $ partial(T)$ for any complete binary tree $T$.
5
Badawi, Ayman, and Roswitha Rissner. "Ramsey numbers of partial order graphs (comparability graphs) and implications in ring theory." Open Mathematics 18, no. 1 (December 31, 2020): 1645–57. http://dx.doi.org/10.1515/math-2020-0085.
Full textAbstract:
Abstract For a partially ordered set (A,\le ) , let {G}_{A} be the simple, undirected graph with vertex set A such that two vertices a\ne b\in A are adjacent if either a\le b or b\le a . We call {G}_{A} the partial order graph or comparability graph of A. Furthermore, we say that a graph G is a partial order graph if there exists a partially ordered set A such that G={G}_{A} . For a class {\mathcal{C}} of simple, undirected graphs and n, m\ge 1 , we define the Ramsey number { {\mathcal R} }_{{\mathcal{C}}}(n,m) with respect to {\mathcal{C}} to be the minimal number of vertices r such that every induced subgraph of an arbitrary graph in {\mathcal{C}} consisting of r vertices contains either a complete n-clique {K}_{n} or an independent set consisting of m vertices. In this paper, we determine the Ramsey number with respect to some classes of partial order graphs. Furthermore, some implications of Ramsey numbers in ring theory are discussed.
6
Hussain, Muhammad, Muhammad Asif, Ashit Kumar Dutta, and Sultan Almotairi. "Upper Bounds of AZI and ABC Index for Transformed Families of Graphs." Mathematical Problems in Engineering 2022 (January 25, 2022): 1–14. http://dx.doi.org/10.1155/2022/4152854.
Full textAbstract:
Topological index is a mapping which corresponds underlying graph with a numeric value and invariant up to all the isomorphisms of graph. Our study is based on a partial open question regarding topological indices: for which members of n-vertex graph family, certain index has minimum or maximum value? In this work, we answered the above-mentioned question regarding AZI and ABC for transformed families of graphs Γ n k , l and A α Γ n k , l . We investigated the fact of pendent paths and the transformation A α over these indices and developed the tight upper bounds regarding these families of graphs. Moreover, we characterized transformed graphs associated with maximum values of these indices.
7
Chen, Xiaolin, and Huishu Lian. "Extremal Matching Energy and the Largest Matching Root of Complete Multipartite Graphs." Complexity 2019 (April 16, 2019): 1–7. http://dx.doi.org/10.1155/2019/9728976.
Full textAbstract:
The matching energy ME(G) of a graph G was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial m(G,x). The largest matching root λ1(G) is the largest root of the matching polynomial m(G,x). Let Kn1,n2,…,nr denote the complete r-partite graph with order n=n1+n2+…+nr, where r>1. In this paper, we prove that, for the given values n and r, both the matching energy ME(G) and the largest matching root λ1(G) of complete r-partite graphs are minimal for complete split graph CS(n,r-1) and are maximal for Turán graph T(n,r).
8
Alrowaili, Dalal Awadh, Uzma Ahmad, Saira Hameeed, and Muhammad Javaid. "Graphs with mixed metric dimension three and related algorithms." AIMS Mathematics 8, no. 7 (2023): 16708–23. http://dx.doi.org/10.3934/math.2023854.
Full textAbstract:
<abstract><p>Let $ G = (V, E) $ be a simple connected graph. A vertex $ x\in V(G) $ resolves the elements $ u, v\in E(G)\cup V(G) $ if $ d_G(x, u)\neq d_G(x, v) $. A subset $ S\subseteq V(G) $ is a mixed metric resolving set for $ G $ if every two elements of $ G $ are resolved by some vertex of $ S $. A set of smallest cardinality of mixed metric generator for $ G $ is called the mixed metric dimension. In this paper trees and unicyclic graphs having mixed dimension three are classified. The main aim is to investigate the structure of a simple connected graph having mixed dimension three with respect to the order of graph, maximum degree of basis elements and distance partite sets of basis elements. In particular to find necessary and sufficient conditions for a graph to have mixed metric dimension 3. Moreover three separate algorithms are developed for trees, unicyclic graphs and in general for simple connected graph $ J_{n}\ncong P_{n} $ with $ n\geq 3 $ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide a mixed basis of an input graph.</p></abstract>
9
Castro, Jair, Ludwin A. Basilio, Gerardo Reyna, and Omar Rosario. "The differential on operator $ {{\mathcal{S}}({\Gamma})} $." Mathematical Biosciences and Engineering 20, no. 7 (2023): 11568–84. http://dx.doi.org/10.3934/mbe.2023513.
Full textAbstract:
<abstract><p>Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of <italic>differential</italic> refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The <italic>differential</italic> of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.</p></abstract>
10
Abiad, Aida, Leonardo De Lima, Dheer Noal Desai, Krystal Guo, Leslie Hogben, and José Madrid. "Positive and negative square energies of graphs." Electronic Journal of Linear Algebra 39 (June 8, 2023): 307–26. http://dx.doi.org/10.13001/ela.2023.7827.
Full textAbstract:
The energy of a graph $G$ is the sum of the absolute values of the eigenvalues of the adjacency matrix of $G$. Let $s^+(G), s^-(G)$ denote the sum of the squares of the positive and negative eigenvalues of $G$, respectively. It was conjectured by [Elphick, Farber, Goldberg, Wocjan, Discrete Math. (2016)] that if $G$ is a connected graph of order $n$, then $s^+(G)\geq n-1$ and $s^-(G) \geq n-1$. In this paper, we show partial results towards this conjecture. In particular, numerous structural results that may help in proving the conjecture are derived, including the effect of various graph operations. These are then used to establish the conjecture for several graph classes, including graphs with certain fraction of positive eigenvalues and unicyclic graphs.
11
BRYANT, DARRYN, and BARBARA MAENHAUT. "COMMON MULTIPLES OF COMPLETE GRAPHS." Proceedings of the London Mathematical Society 86, no. 2 (March 2003): 302–26. http://dx.doi.org/10.1112/s0024611502013771.
Full textAbstract:
A graph $H$ is said to divide a graph $G$ if there exists a set $S$ of subgraphs of $G$, all isomorphic to $H$, such that the edge set of $G$ is partitioned by the edge sets of the subgraphs in $S$. Thus, a graph $G$ is a common multiple of two graphs if each of the two graphs divides $G$. This paper considers common multiples of a complete graph of order $m$ and a complete graph of order $n$. The complete graph of order $n$ is denoted $K_n$. In particular, for all positive integers $n$, the set of integers $q$ for which there exists a common multiple of $K_3$ and $K_n$ having precisely $q$ edges is determined.It is shown that there exists a common multiple of $K_3$ and $K_n$ having $q$ edges if and only if $q \equiv 0 \, ({\rm mod}\, 3)$, $q \equiv 0 \, ({\rm mod}\, \binom n2)$ and(1) $q \neq 3 \binom n2$ when $n \equiv 5 \, ({\rm mod}\, 6)$; (2) $q \geq (n + 1) \binom n2$ when $n$ is even; (3) $q \notin \{36, 42, 48\}$ when $n = 4$.The proof of this result uses a variety of techniques including the use of Johnson graphs, Skolem and Langford sequences, and equitable partial Steiner triple systems.2000 Mathematical Subject Classification: 05C70, 05B30, 05B07.
12
Bhat, K. Arathi, and G. Sudhakara. "Commuting decomposition of Kn1,n2,...,nk through realization of the product A(G)A(GPk )." Special Matrices 6, no. 1 (August 1, 2018): 343–56. http://dx.doi.org/10.1515/spma-2018-0028.
Full textAbstract:
Abstract In this paper, we introduce the notion of perfect matching property for a k-partition of vertex set of given graph. We consider nontrivial graphs G and GPk , the k-complement of graph G with respect to a kpartition of V(G), to prove that A(G)A(GPk ) is realizable as a graph if and only if P satis_es perfect matching property. For A(G)A(GPk ) = A(Γ) for some graph Γ, we obtain graph parameters such as chromatic number, domination number etc., for those graphs and characterization of P is given for which GPk and Γ are isomorphic. Given a 1-factor graph G with 2n vertices, we propose a partition P for which GPk is a graph of rank r and A(G)A(GPk ) is graphical, where n ≤ r ≤ 2n. Motivated by the result of characterizing decomposable Kn,n into commuting perfect matchings [2], we characterize complete k-partite graph Kn1,n2,...,nk which has a commuting decomposition into a perfect matching and its k-complement.
13
Agnes, Sheeba. "Degree distance of tensor product and strong product of graphs." Filomat 28, no. 10 (2014): 2185–98. http://dx.doi.org/10.2298/fil1410185a.
Full textAbstract:
In this paper, we determine the degree distance of G x Kr0,r1,...,rn-1 and G ? Kr0,r1,...,rn-1, where x and ? denote the tensor product and strong product of graphs, respectively, and Kr0,r1,...,rn-1 denotes the complete multipartite graph with partite sets V0,V1,...,Vn-1 where |Vj| = rj, 0 ? j ? n - 1 and n ? 3. Using the formulae obtained here, we have obtained the exact value of the degree distance of some classes of graphs.
14
PAULRAJA, P., and V. SHEEBA AGNES. "CONNECTIVITY OF TENSOR PRODUCT OF GRAPHS." Discrete Mathematics, Algorithms and Applications 05, no. 04 (December 2013): 1350023. http://dx.doi.org/10.1142/s1793830913500237.
Full textAbstract:
In this paper, we determine the connectivity of G × Kr0,r1,…,rn-1, where × denotes the tensor product of graphs and Kr0,r1,…,rn-1 denotes the complete n-partite graph with [Formula: see text], and n ≥ 3. The main result of this paper deduces the main result of the paper appeared in Discrete Math. 311 (2011) 2563–2565 as a corollary.
15
Yang, Ruosong, and Ligong Wang. "Distance integral complete r-partite graphs." Filomat 29, no. 4 (2015): 739–49. http://dx.doi.org/10.2298/fil1504739y.
Full textAbstract:
Let D(G)=(dij)nxn denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In this paper, we investigate distance integral complete r-partite graphs Kp1,p2,...,pr = Ka1?p1,a2?p2,...,as?ps and give a sufficient and necessary condition for Ka1?p1,a2?p2,...,as?ps to be distance integral, from which we construct infinitely many new classes of distance integral graphs with s = 1,2,3,4. Finally, we propose two basic open problems for further study.
16
Gao, Fang, Xiaoxin Li, Kai Zhou, and Jia-Bao Liu. "The Extremal Graphs of Some Topological Indices with Given Vertex k-Partiteness." Mathematics 6, no. 11 (November 21, 2018): 271. http://dx.doi.org/10.3390/math6110271.
Full textAbstract:
The vertex k-partiteness of graph G is defined as the fewest number of vertices whose deletion from G yields a k-partite graph. In this paper, we characterize the extremal value of the reformulated first Zagreb index, the multiplicative-sum Zagreb index, the general Laplacian-energy-like invariant, the general zeroth-order Randić index, and the modified-Wiener index among graphs of order n with vertex k-partiteness not more than m .
17
Gervacio, Severino V. "Resistance distance in complete n-partite graphs." Discrete Applied Mathematics 203 (April 2016): 53–61. http://dx.doi.org/10.1016/j.dam.2015.09.017.
Full text
18
MUBAYI, DHRUV. "Some Exact Results and New Asymptotics for Hypergraph Turán Numbers." Combinatorics, Probability and Computing 11, no. 3 (May 2002): 299–309. http://dx.doi.org/10.1017/s0963548301005028.
Full textAbstract:
Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C(r)4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1 [les ] … [les ] sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.Füredi conjectured over 15 years ago that ex(n,C(3)4) [les ] (n2) for sufficiently large n. We prove the weaker resultex(n, {C(3)4, K(3)(1,2,4)}) [les ] (n2).Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture thatex(n, K(r)(s1,…,sr)) = Θ(nr−1/s),where s = Πr−1i=1si. We prove this conjecture when s1 = … = sr−2 = 1 and(i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!.In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)).We also provide an explicit construction givingex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3.This improves upon the previous best lower bound of Ω(n29/11) obtained by probabilistic methods. Several related open problems are also presented.
19
Hidayat, Wahyu, and Elin Herlinawati. "Characterization of Directed Graphs Representing C*-Algebra of Complex Matrices." E3S Web of Conferences 483 (2024): 03004. http://dx.doi.org/10.1051/e3sconf/202448303004.
Full textAbstract:
Quantum mechanics is a study that plays a major role in determining the biological intelligence of Artificial Intelligence (AI). Point particle systems in quantum mechanics can be explained using C*-Algebra which is called CAR-algebra. There is a special case in the CAR-algebra which is isomorphic to the C*-algebra of complex matrices. On the other hand, C*-algebras of direct sum of complex matrix spaces is isomorphic to C*-algebra constructed by orthogonal projection and partial isometries operators via the Cuntz-Krieger relations of a directed graph. This article will provide a basis for the relationship between quantum mechanics and graphs through a discussion of the characterization of graphs that can represent C*-algebra of complex matrices. It is found that C*-algebra complex matrices n × n is a directed graph without cycles with n – 1 arrows, a single source, and has n path from the source.
20
Bennett, Patrick, Andrzej Dudek, Bernard Lidický, and Oleg Pikhurko. "Minimizing the number of 5-cycles in graphs with given edge-density." Combinatorics, Probability and Computing 29, no. 1 (October 9, 2019): 44–67. http://dx.doi.org/10.1017/s0963548319000257.
Full textAbstract:
AbstractMotivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.
21
Brückner, Guido, Nadine Krisam, and Tamara Mchedlidze. "Level-Planar Drawings with Few Slopes." Algorithmica 84, no. 1 (November 19, 2021): 176–96. http://dx.doi.org/10.1007/s00453-021-00884-x.
Full textAbstract:
AbstractWe introduce and study level-planar straight-line drawings with a fixed number $$\lambda $$ λ of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an $$O(n \log ^2 n / \log \log n)$$ O ( n log 2 n / log log n ) -time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present $$O(n^{4/3} \log n)$$ O ( n 4 / 3 log n ) -time and $$O(\lambda n^{10/3} \log n)$$ O ( λ n 10 / 3 log n ) -time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with $$\lambda $$ λ slopes is -hard even in restricted cases.
22
NIKIFOROV, VLADIMIR. "A Spectral Erdős–Stone–Bollobás Theorem." Combinatorics, Probability and Computing 18, no. 3 (May 2009): 455–58. http://dx.doi.org/10.1017/s0963548309009687.
Full textAbstract:
Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies then G contains a complete r-partite subgraph with r − 1 parts of size ⌊(c/rr)r log n⌋ and one part of size greater than n1−cr−1.This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F1, F2, . . . are r-chromatic graphs satisfying v(Fn) = o(log n), then
23
BALOGH, JÓZSEF, CHOONGBUM LEE, and WOJCIECH SAMOTIJ. "Corrádi and Hajnal's Theorem for Sparse Random Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (February 2, 2012): 23–55. http://dx.doi.org/10.1017/s0963548311000642.
Full textAbstract:
In this paper we extend a classical theorem of Corrádi and Hajnal into the setting of sparse random graphs. We show that ifp(n) ≫ (logn/n)1/2, then asymptotically almost surely every subgraph ofG(n,p) with minimum degree at least (2/3 +o(1))npcontains a triangle packing that covers all but at mostO(p−2) vertices. Moreover, the assumption onpis optimal up to the (logn)1/2factor and the presence of the set ofO(p−2) uncovered vertices is indispensable. The main ingredient in the proof, which might be of independent interest, is an embedding theorem which says that if one imposes certain natural regularity conditions on all three pairs in a balanced 3-partite graph, then this graph contains a perfect triangle packing.
24
Qingxue, Huang. "Complete multipartite decompositions of complete graphs and complete n-partite graphs." Applied Mathematics-A Journal of Chinese Universities 18, no. 3 (September 2003): 352–60. http://dx.doi.org/10.1007/s11766-003-0061-y.
Full text
25
Alon, Noga. "Choice Numbers of Graphs: a Probabilistic Approach." Combinatorics, Probability and Computing 1, no. 2 (June 1992): 107–14. http://dx.doi.org/10.1017/s0963548300000122.
Full textAbstract:
The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). By applying probabilistic methods, it is shown that there are two positive constants c1 and c2 such that for all m ≥ 2 and r ≥ 2 the choice number of the complete r-partite graph with m vertices in each vertex class is between c1r log m and c2r log m. This supplies the solutions of two problems of Erdős, Rubin and Taylor, as it implies that the choice number of almost all the graphs on n vertices is o(n) and that there is an n vertex graph G such that the sum of the choice number of G with that of its complement is at most O(n1/2(log n)1/2).
26
RAMOS, ÁLVARO KRÜGER. "THE MEAN CURVATURE EQUATION ON SEMIDIRECT PRODUCTS : HEIGHT ESTIMATES AND SCHERK-LIKE GRAPHS." Journal of the Australian Mathematical Society 101, no. 1 (February 26, 2016): 118–44. http://dx.doi.org/10.1017/s1446788715000713.
Full textAbstract:
In the ambient space of a semidirect product $\mathbb{R}^{2}\rtimes _{A}\mathbb{R}$, we consider a connected domain ${\rm\Omega}\subseteq \mathbb{R}^{2}\rtimes _{A}\{0\}$. Given a function $u:{\rm\Omega}\rightarrow \mathbb{R}$, its ${\it\pi}$-graph is $\text{graph}(u)=\{(x,y,u(x,y))\mid (x,y,0)\in {\rm\Omega}\}$. In this paper we study the partial differential equation that $u$ must satisfy so that $\text{graph}(u)$ has prescribed mean curvature $H$. Using techniques from quasilinear elliptic equations we prove that if a ${\it\pi}$-graph has a nonnegative mean curvature function, then it satisfies some uniform height estimates that depend on ${\rm\Omega}$ and on the supremum the function attains on the boundary of ${\rm\Omega}$. When $\text{trace}(A)>0$, we prove that the oscillation of a minimal graph, assuming the same constant value $n$ along the boundary, tends to zero when $n\rightarrow +\infty$ and goes to $+\infty$ if $n\rightarrow -\infty$. Furthermore, we use these estimates, allied with techniques from Killing graphs, to prove the existence of minimal ${\it\pi}$-graphs assuming the value zero along a piecewise smooth curve ${\it\gamma}$ with endpoints $p_{1},\,p_{2}$ and having as boundary ${\it\gamma}\cup (\{p_{1}\}\times [0,\,+\infty ))\cup (\{p_{2}\}\times [0,\,+\infty ))$.
27
Bień, Anna. "Gamma Graphs Of Some Special Classes Of Trees." Annales Mathematicae Silesianae 29, no. 1 (September 1, 2015): 25–34. http://dx.doi.org/10.1515/amsil-2015-0003.
Full textAbstract:
AbstractA set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G).Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs γ.T of trees with diameter not greater than five will be presented. It will be shown that hypercubes Qk are among γ.T graphs. In the third section γ.T graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented, in response to an open question, published by Fricke et al., if diam(T (γ)) = O(n)?
28
Hwang, Shiow-Fen, and Gerard J. Chang. "Edge domatic numbers of complete n- partite graphs." Graphs and Combinatorics 10, no. 2-4 (June 1994): 241–48. http://dx.doi.org/10.1007/bf02986672.
Full text
29
Cabulao, Jessa Mae Carpentero, and Rowena T. Isla. "On Connected Partial Domination in Graphs." European Journal of Pure and Applied Mathematics 14, no. 4 (November 10, 2021): 1490–506. http://dx.doi.org/10.29020/nybg.ejpam.v14i4.4168.
Full textAbstract:
This paper introduces and investigates a variant of partial domination called the connected α-partial domination. For any graph G = (V (G), E(G)) and α ∈ (0, 1], a set S ⊆ V (G) is an α-partial dominating set in G if |N[S]| ≥ α |V (G)|. An α-partial dominating set S ⊆ V (G) is a connected α-partial dominating set in G if ⟨S⟩, the subgraph induced by S, is connected. The connected α-partial domination number of G, denoted by ∂Cα(G), is the smallest cardinality of a connected α-partial dominating set in G. In this paper, we characterize the connected α-partial dominating sets in the join and lexicographic product of graphs for any α ∈ (0, 1] and determine the corresponding connected α-partial domination numbers of graphs resulting from the said binary operations. Moreover, we establish sharp bounds for the connected α-partial domination numbers of the corona and Cartesian product of graphs. Furthermore, we determine ∂Cα(G) of some special graphs when α =1/2. Several realization problems are also generated in this paper.
30
Garamvölgyi, Dániel, and Tibor Jordán. "Graph Reconstruction from Unlabeled Edge Lengths." Discrete & Computational Geometry 66, no. 1 (February 26, 2021): 344–85. http://dx.doi.org/10.1007/s00454-021-00275-7.
Full textAbstract:
AbstractA d-dimensional framework is a pair (G, p), where $$G=(V,E)$$ G = ( V , E ) is a graph and p is a map from V to $$\mathbb {R}^d$$ R d . The length of an edge $$uv\in E$$ u v ∈ E in (G, p) is the distance between p(u) and p(v). The framework is said to be globally rigid in $$\mathbb {R}^d$$ R d if every other d-dimensional framework (G, q), in which the corresponding edge lengths are the same, is congruent to (G, p). In a recent paper Gortler, Theran, and Thurston proved that if every generic framework (G, p) in $$\mathbb {R}^d$$ R d is globally rigid for some graph G on $$n\ge d+2$$ n ≥ d + 2 vertices (where $$d\ge 2$$ d ≥ 2 ), then already the set of (unlabeled) edge lengths of a generic framework (G, p), together with n, determine the framework up to congruence. In this paper we investigate the corresponding unlabeled reconstruction problem in the case when the above generic global rigidity property does not hold for the graph. We provide families of graphs G for which the set of (unlabeled) edge lengths of any generic framework (G, p) in d-space, along with the number of vertices, uniquely determine the graph, up to isomorphism. We call these graphs weakly reconstructible. We also introduce the concept of strong reconstructibility; in this case the labeling of the edges is also determined by the set of edge lengths of any generic framework. For $$d=1,2$$ d = 1 , 2 we give a partial characterization of weak reconstructibility as well as a complete characterization of strong reconstructibility of graphs. In particular, in the low-dimensional cases we describe the family of weakly reconstructible graphs that are rigid but not redundantly rigid.
31
Koponen, Vera. "A Limit Law of Almost l-partite Graphs." Journal of Symbolic Logic 78, no. 3 (September 2013): 911–36. http://dx.doi.org/10.2178/jsl.7803110.
Full textAbstract:
AbstractFor integers l ≥ 1, d ≥ 0 we study (undirected) graphs with vertices 1, …, n such that the vertices can be partitioned into l parts such that every vertex has at most d neighbours in its own part. The set of all such graphs is denoted Pn (l, d). We prove a labelled first-order limit law, i.e., for every first-order sentence φ, the proportion of graphs in Pn (l, d) that satisfy φ converges as n → ∞. By combining this result with a result of Hundack, Prömel and Steger [12] we also prove that if 1 ≤ s1 ≤ … ≤ sl are integers, then Forb() has a labelled first-order limit law, where Forb() denotes the set of all graphs with vertices 1, …, n, for some n, in which there is no subgraph isomorphic to the complete (l + 1 )-partite graph with parts of sizes 1, s1, …, sl. In the course of doing this we also prove that there exists a first-order formula ξ, depending only on l and d, such that the proportion of ∈ Pn (l, d) with the following property approaches 1 as n → ∞: there is a unique partition of {1, …, n} into l parts such that every vertex has at most d neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by ξ.
32
Zhang, Zhiqiang, Tariq Mehmood, Atiq ur Rehman, Muhammad Hussain, and Xiujun Zhang. "On Valuation of Edge Irregularity Strength of Certain Graphical Families." Journal of Mathematics 2022 (November 28, 2022): 1–8. http://dx.doi.org/10.1155/2022/3230932.
Full textAbstract:
This article comprises of exact valuation of a graph parameter, known as the edge irregularity strength EIS , symbolized as eis G , of various graphical families such as middle graph of path graph, middle graph of cycle graph, snake graph (string 2), paramedian ladder, and complete m -partite graphs. If δ : V ⟶ 1,2 , … , p is a function defined on vertices of a graph that helps to determine different weights for every pair of edges, the least value of p is the target. Thus, addition operation for allocated to vertices of an edge, i.e., δ v i + δ v j , i ≠ j = 1,2 , … , n , defines the weight w δ v i v j of corresponding edge for every v i v j ∈ E . If two different edges e i and e j in graph G carry weights in different manner, i.e., w δ e i ≠ w δ e i for i ≠ j . Then the edge irregular p -labeling is defined after a vertex p -labeling of G . After establishing various novel results and making some conclusions, an open problem is mentioned in the end.
33
Bian, Jicheng, Da Huang, Jiabo Xu, and Zhiyong Yu. "Consensus-Related Performance of Triplex MASs Based on Partial Complete Graph Structure." Entropy 24, no. 9 (September 14, 2022): 1296. http://dx.doi.org/10.3390/e24091296.
Full textAbstract:
This article mainly studies first-order coherence related to the robustness of the triplex MASs consensus models with partial complete graph structures; the performance index is studied through algebraic graph theory. The topologies of the novel triplex networks are generated by graph operations and the approach of graph spectra is applied to calculate the first-order network coherence. The coherence asymptotic behaviours of the three cases of the partial complete structures are analysed and compared. We find that under the condition that the number of nodes in partial complete substructures n tends to infinity, the coherence asymptotic behaviour of the two sorts of non-isomorphic three-layered networks will be increased by r−12(r+1), which is irrelevant to the peripheral vertices number p; when p tends to infinity, adding star copies to the original triplex topologies will reverse the original size relationship of the coherence under consideration of the triplex networks. Finally, the coherence of the three-layered networks with the same sorts of parameters, but non-isomorphic graphs, are simulated to verify the results.
34
An, Junfeng, and Yingzhi Tian. "Graphs with a given conditional diameter that maximize the Wiener index." AIMS Mathematics 9, no. 6 (2024): 15928–36. http://dx.doi.org/10.3934/math.2024770.
Full textAbstract:
<abstract><p>The Wiener index $ W(G) $ of a graph $ G $ is one of the most well-known topological indices, which is defined as the sum of distances between all pairs of vertices of $ G $. The diameter $ D(G) $ of $ G $ is the maximum distance between all pairs of vertices of $ G $, and the conditional diameter $ D(G; s) $ is the maximum distance between all pairs of vertex subsets with cardinality $ s $ of $ G $. When $ s = 1 $, the conditional diameter $ D(G; s) $ is just the diameter $ D(G) $. The authors in <sup>[<xref ref-type="bibr" rid="b18">18</xref>]</sup> characterized the graphs with the maximum Wiener index among all graphs with diameter $ D(G) = n-c $, where $ 1\le c\le 4 $. In this paper, we will characterize the graphs with the maximum Wiener index among all graphs with conditional diameter $ D(G; s) = n-2s-c $ ($ -1\leq c\leq 1 $), which extends partial results above.</p></abstract>
35
Gao, Wei, Jie Han, and Yi Zhao. "Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles." Combinatorics, Probability and Computing 28, no. 06 (July 9, 2019): 840–70. http://dx.doi.org/10.1017/s096354831900021x.
Full textAbstract:
AbstractGiven two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K(k)(1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.
36
DANCIULESCU, DANIELA, and MIHAELA COLHON. "Systems of knowledge representation based on stratified graphs. Application in Natural Language Generation." Carpathian Journal of Mathematics 32, no. 1 (2016): 49–62. http://dx.doi.org/10.37193/cjm.2016.01.05.
Full textAbstract:
The concept of stratified graph introduces some method of knowledge representation (see [T¸ and ˘ areanu, N., ˘ Knowledge representation by labeled stratified graphs, Proc. 8th World Multi-Conference on Systemics, Cybernetics and Informatics, 5 (2004), 345–350; T¸ and ˘ areanu, N., ˘ Proving the Existence of Labelled Stratified Graphs, An. Univ. Craiova Ser. Mat. Inform., 27 (2000), 81–92]) The inference process developed for this method uses the paths of the stratified graphs, an order between the elementary arcs of a path and some results of universal algebras. The order is defined by considering a structured path instead of a regular path. In this paper we define the concept of system of knowledge representation as a tuple of the following components: a stratified graph G, a partial algebra Y of real objects, an embedding mapping (an injective mapping that embeds the nodes of G into objects of Y ) and a set of algorithms such that each of them can combine two objects of Y to get some other object of Y . We define also the concept of inference process performed by a system of knowledge processing in which the interpretation of the symbolic elements is defined by means of natural language constructions. In this manner we obtained a mechanism for texts generation in a natural language (for this approach, Romanian).
37
Ortner, Ronald, and Wolfgang Woess. "Non-Backtracking Random Walks and Cogrowth of Graphs." Canadian Journal of Mathematics 59, no. 4 (August 1, 2007): 828–44. http://dx.doi.org/10.4153/cjm-2007-035-1.
Full textAbstract:
AbstractLet X be a locally finite, connected graph without vertices of degree 1. Non-backtracking random walk moves at each step with equal probability to one of the “forward” neighbours of the actual state, i.e., it does not go back along the preceding edge to the preceding state. This is not a Markov chain, but can be turned into a Markov chain whose state space is the set of oriented edges of X. Thus we obtain for infinite X that the n-step non-backtracking transition probabilities tend to zero, and we can also compute their limit when X is finite. This provides a short proof of an old result concerning cogrowth of groups, and makes the extension of that result to arbitrary regular graphs rigorous. Even when X is non-regular, but small cycles are dense in X, we show that the graph X is non-amenable if and only if the non-backtracking n-step transition probabilities decay exponentially fast. This is a partial generalization of the cogrowth criterion for regular graphs which comprises the original cogrowth criterion for finitely generated groups of Grigorchuk and Cohen.
38
Lam, Peter Che Bor, Wai Chee Shiu, Chong Sze Tong, and Zhong Fu Zhang. "On the equitable chromatic number of complete n-partite graphs." Discrete Applied Mathematics 113, no. 2-3 (October 2001): 307–10. http://dx.doi.org/10.1016/s0166-218x(00)00296-1.
Full text
39
Mari, Baskar, and Ravi Sankar Jeyaraj. "Radio number of $ 2- $ super subdivision for path related graphs." AIMS Mathematics 9, no. 4 (2024): 8214–29. http://dx.doi.org/10.3934/math.2024399.
Full textAbstract:
<abstract><p>We studied radio labelings of graphs in response to the Channel Assignment Problem (CAP). In a graph $ G, $ the radio labeling is a mapping $ \varpi:V(G) \rightarrow \{0, 1, 2, ..., \}, $ such as $ |\varpi(\mu')-\varpi(\mu'')|\geq diam(G)+1-d(\mu', \mu''). $ The label of $ \mu $ for under $ \varpi $ is defined by the integer $ \varpi(\mu), $ and the span under is defined by $ span(\varpi) = max \{|\varpi(\mu')-\varpi(\mu'')|: \mu', \mu'' \in V(G)\}. $ $ rn(G) = min_{\varpi} span(\varpi) $ is defined as the radio number of $ G $ when the minimum over all radio labeling $ \varpi $ of $ G $ is taken. $ G $ is said to be optimal if its radio labeling is $ span(\varpi) = rn(G). $ A graph H is said to be an $ m $ super subdivision if $ G $ is replaced by the complete bipartite graph $ K_{m, m} $ with $ m = 2 $ in such a way that the end vertices of the edge are merged with any two vertices of the same partite set $ X $ or $ Y $ of $ K_{m, m} $ after removal of the edge of $ G $. Up to this point, many lower and upper bounds of $ rn(G) $ have been found for several kinds of graph families. This work presents a comprehensive analysis of the radio number $ rn(G) $ for a graph $ G $, with particular emphasis on the $ m $ super subdivision of a path $ P_{n} $ with $ n (n \geq 3) $ vertices, along with a complete bipartite graph $ K_{m, m} $ consisting of $ m $ v/ertices, where $ m = 2 $.</p></abstract>
40
Prestin, Jürgen, and Ewald Quak. "On the arclength of trigonometric interpolants." Journal of Numerical Analysis and Approximation Theory 30, no. 2 (August 1, 2001): 219–27. http://dx.doi.org/10.33993/jnaat302-699.
Full textAbstract:
As pointed out recently by Strichartz [5], the arclength of the graph \(\Gamma(S_N(f))\) of the partial sums \(S_N(f)\) of the Fourier series of a jump function \(f\) grows with the order of \(\log N\).In this paper we discuss the behaviour of the arclengths of the graphs of trigonometric interpolants to a jump function. Here the boundedness of the arclengths depends essentially on the fact whether the jump discontinuity is at an interpolation point or not.
In addition convergence results for the arclengths of interpolants to smoother functions are presented.
41
JANZING, DOMINIK, PAWEL WOCJAN, and THOMAS BETH. "ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING ARBITRARY INTERACTION GRAPHS." International Journal of Foundations of Computer Science 14, no. 05 (October 2003): 889–903. http://dx.doi.org/10.1142/s0129054103002072.
Full textAbstract:
The most popular model of quantum computation is the quantum circuit model using single and two qubit gates as elementary transformations. Definitions of quantum complexity usually refer to this model. In contrast, we consider the physical interactions among the qubits as the basic computational resource that allows to carry out complex transformations on the quantum register. One method to compare the computational power of different interactions is to examine the complexity of the so-called mutual simulation of interaction Hamiltonians. The physical interaction can simulate other interactions by interspersing the natural time evolution with external control operations. In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for simulations of general interaction graphs. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.
42
Lingas, Andrzej, Mateusz Miotk, Jerzy Topp, and Paweł Żyliński. "Graphs with equal domination and covering numbers." Journal of Combinatorial Optimization 39, no. 1 (October 25, 2019): 55–71. http://dx.doi.org/10.1007/s10878-019-00454-6.
Full textAbstract:
Abstract A dominating set of a graph G is a set $$D\subseteq V_G$$D⊆VG such that every vertex in $$V_G-D$$VG-D is adjacent to at least one vertex in D, and the domination number $$\gamma (G)$$γ(G) of G is the minimum cardinality of a dominating set of G. A set $$C\subseteq V_G$$C⊆VG is a covering set of G if every edge of G has at least one vertex in C. The covering number $$\beta (G)$$β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which $$\gamma (G)=\beta (G)$$γ(G)=β(G) is denoted by $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β, whereas $${\mathcal {B}}$$B denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β and $${\mathcal {B}}$$B. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to $${\mathcal {B}}$$B, and, as a side result, we conclude that the algorithm of Arumugam et al. (Discrete Appl Math 161:1859–1867, 2013) allows to recognize all the graphs belonging to the set $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that it can be solved in $$O(n \log n + m)$$O(nlogn+m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.
43
Macapodi, Roselainie Dimasindil, and Rowena Isla. "Total Partial Domination in Graphs Under Some Binary Operations." European Journal of Pure and Applied Mathematics 12, no. 4 (October 31, 2019): 1643–55. http://dx.doi.org/10.29020/nybg.ejpam.v12i4.3554.
Full textAbstract:
Let G = (V (G), E(G)) be a simple graph and let α ∈ (0, 1]. A set S ⊆ V (G) isan α-partial dominating set in G if |N[S]| ≥ α |V (G)|. The smallest cardinality of an α-partialdominating set in G is called the α-partial domination number of G, denoted by ∂α(G). An α-partial dominating set S ⊆ V (G) is a total α-partial dominating set in G if every vertex in S isadjacent to some vertex in S. The total α-partial domination number of G, denoted by ∂T α(G), isthe smallest cardinality of a total α-partial dominating set in G. In this paper, we characterize thetotal partial dominating sets in the join, corona, lexicographic and Cartesian products of graphsand determine the exact values or sharp bounds of the corresponding total partial dominationnumber of these graphs.
44
JUKNA, S., and G. SCHNITGER. "Triangle-Freeness is Hard to Detect." Combinatorics, Probability and Computing 11, no. 6 (November 2002): 549–69. http://dx.doi.org/10.1017/s0963548302005333.
Full textAbstract:
We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.
45
Prokopenkov, Vladymyr. "ANALYSIS OF THE DEFERRED SOLUTIONS METHOD FOR FINDING OF HAMILTONIAN CYCLE ON A GRAPH." Bulletin of the NTU "KhPI". Series: Strategic management, portfolio, program and project management, no. 1(7) (November 4, 2023): 60–67. http://dx.doi.org/10.20998/2413-3000.2023.7.8.
Full textAbstract:
The subject of research is the solving of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The purpose of the work is to develop an effective polynomial algorithm for its optimal solving. This work is a continuation of the author's previous work, where the method of deferred solutions is proposed, which uses a iterating over acceptable solutions scheme, which is explaining by the inability to formulate conditions for directly finding the optimal solution. For a graph of n vertices, the size of the iteration space is (n-1)!. For large values n, the time costs are unacceptably large and their reduction is required. During the operation of the deferred solutions method, until the generated solution of the problem becomes a Hamiltonian cycle, it has name – a partial solution. The scheme underlying the deferred solutions method provides: the rejection of the complete construction of all solutions, the simultaneous formation of a set of partial solutions, the discarding of unpromising solutions, the possibility of returning to deferred partial solutions if necessary, the exclusion of the loss of the optimal solution when discarding partial solutions. However, as shown, only when choosing the correct estimate of partial solutions. At first, the real length of the partial solution path was using as an estimate. For an incomplete graph of 20 vertices, the optimal solution found in 0.005 minutes, but on a complete graph of 20 vertices, the search time was commensurate with the search of all possible solutions to the problem. The article analyzes and shows that the real length of the path as an estimate is logically justified and guarantees finding the optimal solution. However, does not always guarantee the minimum time spent searching for it, since when searching through the space of acceptable solutions, a search in width scheme worked out, which entails the construction of almost all acceptable solutions. This explains the different time spent on finding the optimal solution for tests incomplete and complete graphs – the sets of acceptable solutions differ significantly. In this work, as an alternative, another estimate is proposing – the path length of the partial solution, measured in the arcs of the graph. As shown that the use of this estimate leads to a search of solutions in depth. This estimate reduces the time to find a solution, but does not guarantee an optimal result. For the successful application of the method, it is necessary to develop a new estimate of partial solutions that would combine the qualities of the estimates considered.
46
Yang, Xue, Hong Bian, Haizheng Yu, and Dandan Liu. "The Local Antimagic Chromatic Numbers of Some Join Graphs." Mathematical and Computational Applications 26, no. 4 (November 22, 2021): 80. http://dx.doi.org/10.3390/mca26040080.
Full textAbstract:
Let G=(V(G),E(G)) be a connected graph with n vertices and m edges. A bijection f:E(G)→{1,2,⋯,m} is an edge labeling of G. For any vertex x of G, we define ω(x)=∑e∈E(x)f(e) as the vertex label or weight of x, where E(x) is the set of edges incident to x, and f is called a local antimagic labeling of G, if ω(u)≠ω(v) for any two adjacent vertices u,v∈V(G). It is clear that any local antimagic labelling of G induces a proper vertex coloring of G by assigning the vertex label ω(x) to any vertex x of G. The local antimagic chromatic number of G, denoted by χla(G), is the minimum number of different vertex labels taken over all colorings induced by local antimagic labelings of G. In this paper, we present explicit local antimagic chromatic numbers of Fn∨K2¯ and Fn−v, where Fn is the friendship graph with n triangles and v is any vertex of Fn. Moreover, we explicitly construct an infinite class of connected graphs G such that χla(G)=χla(G∨K2¯), where G∨K2¯ is the join graph of G and the complement graph of complete graph K2. This fact leads to a counterexample to a theorem of Arumugam et al. in 2017, and our result also provides a partial solution to Problem 3.19 in Lau et al. in 2021.
47
VOIGT, M. "Algorithmic Aspects of Partial List Colourings." Combinatorics, Probability and Computing 9, no. 4 (July 2000): 375–80. http://dx.doi.org/10.1017/s0963548300004259.
Full textAbstract:
Let G = (V, E) be a graph with n vertices, chromatic number χ(G) and list chromatic number χ[lscr ](G). Suppose each vertex of V(G) is assigned a list of t colours. Albertson, Grossman and Haas [1] conjectured that at least [formula here] vertices can be coloured properly from these lists.Albertson, Grossman and Haas [1] and Chappell [3] proved partial results concerning this conjecture. This paper presents algorithms that colour at least the number of vertices given in the bounds of Albertson, Grossman and Haas, and Chappell. In particular, it follows that the conjecture is valid for all bipartite graphs and that, for every bipartite graph and every assignment of lists with t colours in each list where 0 [les ] t [les ] χ[lscr ](G), it is possible to colour at least (1 − (1/2)t)n vertices in polynomial time. Thus, if G is bipartite and [Lscr ] is a list assignment with [mid ]L(v)[mid ] [ges ] log2n for all v ∈ V, then G is [Lscr ]-list colourable in polynomial time.
48
ZHAO, YUFEI. "On the Lower Tail Variational Problem for Random Graphs." Combinatorics, Probability and Computing 26, no. 2 (August 16, 2016): 301–20. http://dx.doi.org/10.1017/s0963548316000262.
Full textAbstract:
We study the lower tail large deviation problem for subgraph counts in a random graph. Let XH denote the number of copies of H in an Erdős–Rényi random graph $\mathcal{G}(n,p)$. We are interested in estimating the lower tail probability $\mathbb{P}(X_H \le (1-\delta) \mathbb{E} X_H)$ for fixed 0 < δ < 1.Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for p ≥ n−αH (and conjecturally for a larger range of p). We study this variational problem and provide a partial characterization of the so-called ‘replica symmetric’ phase. Informally, our main result says that for every H, and 0 < δ < δH for some δH > 0, as p → 0 slowly, the main contribution to the lower tail probability comes from Erdős–Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite H and δ close to 1.
49
Ni, Zhenyu, Jing Wang, and Liying Kang. "Spectral Extremal Graphs for Disjoint Cliques." Electronic Journal of Combinatorics 30, no. 1 (January 27, 2023). http://dx.doi.org/10.37236/11516.
Full textAbstract:
Let $kK_{r+1}$ be the graph consisting of $k$ vertex-disjoint copies of the complete graph $K_{r+1}$. Moon [Canad. J. Math. 20 (1968) 95--102] and Simonovits [Theory of Graphs (Proc. colloq., Tihany, 1996)] independently showed that if $n$ is sufficiently large, then the join of a complete graph $K_{k-1}$ and an $r$-partite Turán graph $T_{n-k+1,r}$ is the unique extremal graph for $kK_{r+1}$. In this paper we consider the graph which has the maximum spectral radius among all graphs without $k$ disjoint cliques. We show that if $G$ attains the maximum spectral radius over all $n$-vertex $kK_{r+1}$-free graphs for sufficiently large $n$, then $G$ is isomorphic to the join of a complete graph $K_{k-1}$ and an $r$-partite Turán graph $T_{n-k+1,r}$.
50
Tenner, Bridget Eileen. "Boolean complexes and boolean numbers." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (January 1, 2010). http://dx.doi.org/10.46298/dmtcs.2833.
Full textAbstract:
International audience The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing combinatorial properties. This work involves joint efforts with Claesson, Kitaev, and Ragnarsson. \par L'ordre de Bruhat munit tout groupe de Coxeter d'une structure de poset. L'idéal composé des éléments de ce poset engendrant des idéaux principaux ordonnés booléens, forme un poset simplicial. Ce poset simplicial définit le complexe booléen pour le groupe. Dans un système de Coxeter de rang n, nous montrons que le complexe booléen est homotopiquement équivalent à un bouquet de sphères de dimension (n-1). Le nombre de ces sphères est le nombre booléen, qui peut être calculé inductivement à partir du système de Coxeter non-étiquetté; définissant ainsi un invariant de graphe. Pour certaines familles de graphes, les nombres booléens satisfont des propriétés combinatoires intriguantes. Ce travail est une collaboration entre Claesson, Kitaev, et Ragnarsson.