Relevant bibliographies by topics / N-part graph / Journal articles
To see the other types of publications on this topic, follow the link: N-part graph.

Journal articles on the topic 'N-part graph'

Author: Grafiati
Published: 25 May 2024
Last updated: 31 July 2025

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 'N-part graph.'

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

Fran, Fransiskus, Alexander, Yundari, Putri Romanda, and Ervina Febyolga. "The Complexity of Octopus Graph, Friendship Graph, and Snail Graph." EduMatSains : Jurnal Pendidikan, Matematika dan Sains 9, no. 1 (2024): 84–101. http://dx.doi.org/10.33541/edumatsains.v9i1.6042.

Full text
Abstract:
Graphs are basic structures that represent objects with nodes and relationships between objects with edges. Trees are one of the parts studied in graph theory along with finding the number of spanning trees of a graph such as octopus graph, friendship graph, and snail graph. The complexity of an octopus graph is strongly dependent on the number and length of tentacles, the complexity of a friendship graph is dependent on the number of triangle cycles, and the complexity of a snail graph is dependent on the number of edges and vertices located in the shell-like part of the snail. To calculate t
APA, Harvard, Vancouver, ISO, and other styles
2

Day, Maxwell Christopher, Frank Christopher Hawthorne, and Ali Rostami. "Bond topology of chain, ribbon and tube silicates. Part II. Geometrical analysis of infinite 1D arrangements of (TO4) n− tetrahedra." Acta Crystallographica Section A Foundations and Advances 80, no. 3 (2024): 258–81. http://dx.doi.org/10.1107/s2053273324002432.

Full text
Abstract:
In Part I of this series, all topologically possible 1-periodic infinite graphs (chain graphs) representing chains of tetrahedra with up to 6–8 vertices (tetrahedra) per repeat unit were generated. This paper examines possible restraints on embedding these chain graphs into Euclidean space such that they are compatible with the metrics of chains of tetrahedra in observed crystal structures. Chain-silicate minerals with T = Si4+ (plus P5+, V5+, As5+, Al3+, Fe3+, B3+, Be2+, Zn2+ and Mg2+) have a grand nearest-neighbour 〈T–T〉 distance of 3.06±0.15 Å and a minimum T...T separation of 3.71 Å betwee
APA, Harvard, Vancouver, ISO, and other styles
3

Ghanbari, Nima, and Saeid Alikhani. "A graph related to the Euler ø function." Mathematical Gazette 107, no. 569 (2023): 263–72. http://dx.doi.org/10.1017/mag.2023.57.

Full text
Abstract:
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph G is a pair G = (V, E), where V and E are the vertex set and the edge set of G, respectively. The order and size of G is the number of vertices and edges of G, respectively. The degree or valency of a vertex u in a graph G (loopless), denoted by deg (u), is the number of edges meeting at u. If, for every vertex ν in G, deg (ν) = k, we say that G is a k-regular graph. The cycle of order n is denoted by Cn and is a connected 2-regular graph. The path gr
APA, Harvard, Vancouver, ISO, and other styles
4

Nofal, Samer. "On finding a satisfactory partition in an undirected graph: algorithm design and results." AIMS Mathematics 9, no. 10 (2024): 27308–29. http://dx.doi.org/10.3934/math.20241327.

Full text
Abstract:
<p>A satisfactory partition is a partition of undirected-graph vertices such that the partition has only two nonempty parts, and every vertex has at least as many adjacent vertices in its part as it has in the other part. Generally, the problem of determining whether a given undirected graph has a satisfactory partition is known to be NP-complete. In this paper, we show that for a given undirected graph with $ n $ vertices, a satisfactory partition (if any exists) can be computed recursively with a recursion tree of depth of $ \mathcal{O}(\ln n) $ in expectation. Subsequently, we show th
APA, Harvard, Vancouver, ISO, and other styles
5

LIN, YAW-LING, and STEVEN S. SKIENA. "COMPLEXITY ASPECTS OF VISIBILITY GRAPHS." International Journal of Computational Geometry & Applications 05, no. 03 (1995): 289–312. http://dx.doi.org/10.1142/s0218195995000179.

Full text
Abstract:
In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove: • Θ(n3) area is necessary and sufficient
APA, Harvard, Vancouver, ISO, and other styles
6

Venkataraman, Yegnanarayanan, George Barnabas, and Bryan Freyberg. "Chromatic Coloring of Distance Graphs V." Journal of Combinatorial Mathematics and Combinatorial Computing 122, no. 1 (2024): 317–24. http://dx.doi.org/10.61091/jcmcc122-26.

Full text
Abstract:
Let G = ( V , E ) be any graph. If there exists an injection f : V → Z , such that | f ( u ) – f ( v ) | is prime for every u v ∈ E , then we say G is a prime distance graph (PDG). The problem of characterizing the family of all prime distance graphs (PDGs) with chromatic number 3 or 4 is challenging. In the fourth part of this series of articles, we determined which fans are PDGs and which wheels are PDGs. In addition, we showed: (1) a chain of n mutually isomorphic PDGs is a PDG, and (2) the Cartesian product of a PDG and a path is a PDG. In this part of the series, we improve (1) by showing
APA, Harvard, Vancouver, ISO, and other styles
7

S., Geetha, and S. Jayakumar Dr. "COMPUTER REPRESENTATION OF GRAPHS USING BINARY LOGIC CODES IN DISCRETE MATHEMATICS." International Journal of Multidisciplinary Research and Modern Education 3, no. 1 (2017): 152–57. https://doi.org/10.5281/zenodo.438946.

Full text
Abstract:
Discrete Mathematics is a fundamental component of mathematics and computer science. It is the study of finite systems. The Digital computer is basically a finite structure and many of its properties can be understood and interpreted within the framework of finite mathematical systems. Graph are represented by means of Diagrams. These Graphs may be considered as Graph of certain relation. Graphs, Directed Graphs appear in many areas of Mathematics and Computer Science. Graphs are defined as an abstract mathematical system. Elements of Graph Theory are indispensable in almost all areas of Compu
APA, Harvard, Vancouver, ISO, and other styles
8

Xu, Chunyan, Rong Liu, Tong Zhang, Zhen Cui, Jian Yang, and Chunlong Hu. "Dual-Stream Structured Graph Convolution Network for Skeleton-Based Action Recognition." ACM Transactions on Multimedia Computing, Communications, and Applications 17, no. 4 (2021): 1–22. http://dx.doi.org/10.1145/3450410.

Full text
Abstract:
In this work, we propose a dual-stream structured graph convolution network ( DS-SGCN ) to solve the skeleton-based action recognition problem. The spatio-temporal coordinates and appearance contexts of the skeletal joints are jointly integrated into the graph convolution learning process on both the video and skeleton modalities. To effectively represent the skeletal graph of discrete joints, we create a structured graph convolution module specifically designed to encode partitioned body parts along with their dynamic interactions in the spatio-temporal sequence. In more detail, we build a se
APA, Harvard, Vancouver, ISO, and other styles
9

Alnefaie, Kholood, Nanggom Gammi, Saifur Rahman, and Shakir Ali. "On Zero-Divisor Graphs of Zn When n Is Square-Free." Axioms 14, no. 3 (2025): 180. https://doi.org/10.3390/axioms14030180.

Full text
Abstract:
In this article, some properties of the zero-divisor graph Γ(Zn) are investigated when n is a square-free positive integer. It is shown that the zero-divisor graph Γ(Zn) of ring Zn is a (2k−2)-partite graph when the prime decomposition of n contains k distinct square-free primes using the method of congruence relation. We present some examples, accompanied by graphic representations, to achieve the desired results. It is also obtained that the zero-divisor graph Γ(Zn) is Eulerian if n is a square-free odd integer. Since Zn is a semisimple ring when n is square-free, the results can be generali
APA, Harvard, Vancouver, ISO, and other styles
10

Zhong, Chuang, and Shuangliang Tian. "Neighbor Sum Distinguishing Edge (Total) Coloring of Generalized Corona Product." Journal of Physics: Conference Series 2381, no. 1 (2022): 012031. http://dx.doi.org/10.1088/1742-6596/2381/1/012031.

Full text
Abstract:
Abstract The coloring theory of graphs is an important part of graph theory research. The key problem of the coloring theory of graphs is to determine the coloring number of each kind of coloring. Traditional coloring concepts mainly include proper vertex coloring, proper edge coloring, proper total coloring, and so on. In recent years, scholars at home and abroad have put forward some new coloring concepts, such as neighbor vertex distinguishing edge (total) coloring, and neighbor sum distinguishing edge (total) coloring, based on traditional coloring concepts and by adding other constraints.
APA, Harvard, Vancouver, ISO, and other styles
11

Sason, Igal. "Observations on graph invariants with the Lovász $ \vartheta $-function." AIMS Mathematics 9, no. 6 (2024): 15385–468. http://dx.doi.org/10.3934/math.2024747.

Full text
Abstract:
<abstract><p>This paper delves into three research directions, leveraging the Lovász $ \vartheta $-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that $ n \geq 14 $, it is constructively proven that there exist connected, i
APA, Harvard, Vancouver, ISO, and other styles
12

Petrenjuk, Volodymyr, and Dmytro Petreniuk. "Models of Klein Surface Obstruction Graphs." Cybernetics and Computer Technologies, no. 1 (March 29, 2024): 47–63. http://dx.doi.org/10.34229/2707-451x.24.1.4.

Full text
Abstract:
The task of researching the structure of graphs of given connectivity, which are obstructions for a given surface of non-oriented kind, and building their models, from which obstruction graphs are formed by removing or compressing a set of edges, is considered. The issue of edge coverage of an obstruction graph of a given kind with a minimum number of quasi-stars with centers – planar graphs that have given sets of points and all edges are significant with respect to the reachability number 2 on the Euclidean plane and has reachability on the projective plane or Klein surface, is considered. K
APA, Harvard, Vancouver, ISO, and other styles
13

Ikhlaq, Hafiz Muhammad, Hafiz Muhammad Afzal Siddiqui, and Muhammad Imran. "A Comparative Study of Three Resolving Parameters of Graphs." Complexity 2021 (December 15, 2021): 1–13. http://dx.doi.org/10.1155/2021/1927181.

Full text
Abstract:
Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f , w = min d w , t , d w , s is referred as distance between f = t s an edge and w a vertex. d w , f 1 ≠ d w , f 2 implies that two
APA, Harvard, Vancouver, ISO, and other styles
14

BEDNARSKA-BZDȨGA, MAŁGORZATA, DAN HEFETZ, MICHAEL KRIVELEVICH, and TOMASZ ŁUCZAK. "Manipulative Waiters with Probabilistic Intuition." Combinatorics, Probability and Computing 25, no. 6 (2015): 823–49. http://dx.doi.org/10.1017/s0963548315000310.

Full text
Abstract:
For positive integersnandqand a monotone graph property$\mathcal{A}$, we consider the two-player, perfect information game WC(n,q,$\mathcal{A}$), which is defined as follows. The game proceeds in rounds. In each round, the first player, called Waiter, offers the second player, called Client,q+ 1 edges of the complete graphKnwhich have not been offered previously. Client then chooses one of these edges which he keeps and the remainingqedges go back to Waiter. If, at the end of the game, the graph which consists of the edges chosen by Client satisfies the property$\mathcal{A}$, then Waiter is de
APA, Harvard, Vancouver, ISO, and other styles
15

Hamidi, Mohammad, and Irina Cristea. "Hyperideal-based zero-divisor graph of the general hyperring $ \mathbb{Z}_{n} $." AIMS Mathematics 9, no. 6 (2024): 15891–910. http://dx.doi.org/10.3934/math.2024768.

Full text
Abstract:
<abstract><p>The aim of this paper is to introduce and study the concept of a hyperideal-based zero-divisor graph associated with a general hyperring. This is a generalized version of the zero-divisor graph associated with a commutative ring. For any general hyperring $ R $ having a hyperideal $ I $, the $ I $-based zero-divisor graph $ \Gamma^{(I)}(R) $ associated with $ R $ is the simple graph whose vertices are the elements of $ R\setminus I $ having their hyperproduct in $ I $, and two distinct vertices are joined by an edge when their hyperproduct has a non-empty intersection
APA, Harvard, Vancouver, ISO, and other styles
16

Erdős, P., A. Hajnal, M. Simonovits, V. T. Sós, and E. Szemerédi. "Turán-Ramsey Theorems and Kp-Independence Numbers." Combinatorics, Probability and Computing 3, no. 3 (1994): 297–325. http://dx.doi.org/10.1017/s0963548300001218.

Full text
Abstract:
Let the Kp-independence number αp (G) of a graph G be the maximum order of an induced subgraph in G that contains no Kp. (So K2-independence number is just the maximum size of an independent set.) For given integers r, p, m > 0 and graphs L1,…,Lr, we define the corresponding Turán-Ramsey function RTp(n, L1,…,Lr, m) to be the maximum number of edges in a graph Gn of order n such that αp(Gn) ≤ m and there is an edge-colouring of G with r colours such that the jth colour class contains no copy of Lj, for j = 1,…, r. In this continuation of [11] and [12], we will investigate the problem where,
APA, Harvard, Vancouver, ISO, and other styles
17

Qin, Chao, Yu Li, Zhongbi Wang, and Guiyun Chen. "Recognition of the symplectic simple group $ PSp_4(p) $ by the order and degree prime-power graph." AIMS Mathematics 9, no. 2 (2023): 2808–23. http://dx.doi.org/10.3934/math.2024139.

Full text
Abstract:
<abstract><p>Let $ G $ be a finite group, $ \operatorname{cd}(G) $ the set of all irreducible character degrees of $ G $, and $ \rho(G) $ the set of all prime divisors of integers in $ \operatorname{cd}(G) $. For a prime $ p $ and a positive integer $ n $, let $ n_p $ denote the $ p $-part of $ n $. The degree prime-power graph of $ G $ is a graph whose vertex set is $ V(G) = \left\{p^{e_p(G)} \mid p \in \rho(G)\right\} $, where $ p^{e_p(G)} = \max \left\{n_p \mid n \in \operatorname{cd}(G)\right\} $, and there is an edge between distinct numbers $ x, y \in V(G) $ if $ x y $ divide
APA, Harvard, Vancouver, ISO, and other styles
18

NIKIFOROV, VLADIMIR. "A Spectral Erdős–Stone–Bollobás Theorem." Combinatorics, Probability and Computing 18, no. 3 (2009): 455–58. http://dx.doi.org/10.1017/s0963548309009687.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
19

Ferber, Asaf, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney. "Friendly bisections of random graphs." Communications of the American Mathematical Society 2, no. 10 (2022): 380–416. http://dx.doi.org/10.1090/cams/13.

Full text
Abstract:
Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph G ( n , 1 / 2 ) \mathbb {G}(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n − o ( n ) n-o(n) vertices have more neighbours in their own part as across. Our proof is constructive, and in the process, we develop a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument.
APA, Harvard, Vancouver, ISO, and other styles
20

Tao Zhang, Mike, Ken Goldberg, Gordon Smith, Robert-Paul Beretty, and Mark Overmars. "Pin design for part feeding." Robotica 19, no. 6 (2001): 695–702. http://dx.doi.org/10.1017/s0263574701003514.

Full text
Abstract:
Industrial parts can be fed (oriented) using a sequence of fixed horizontal pins to topple the parts as they move past on a conveyor belt. We give an algorithm for designing a sequence of such pins for a given part. Given the n-sided convex polygonal projection of a part, its center of mass and frictional coefficients, our O(n2) algorithm computes the toppling graph, a new data structure that explicitly represents the mechanics of toppling, rolling, and jamming. We verify the toppling graph analysis with experiments. Our O(n3n) design algorithm uses the toppling graph to design a sequence of p
APA, Harvard, Vancouver, ISO, and other styles
21

DING, GUOLI, and STAN DZIOBIAK. "Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs." Combinatorics, Probability and Computing 19, no. 4 (2010): 579–91. http://dx.doi.org/10.1017/s0963548310000076.

Full text
Abstract:
Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove
APA, Harvard, Vancouver, ISO, and other styles
22

MORRISON, SCOTT, DAVID PENNEYS, EMILY PETERS, and NOAH SNYDER. "SUBFACTORS OF INDEX LESS THAN 5, PART 2: TRIPLE POINTS." International Journal of Mathematics 23, no. 03 (2012): 1250016. http://dx.doi.org/10.1142/s0129167x11007586.

Full text
Abstract:
We summarize the known obstructions to subfactors with principal graphs which begin with a triple point. One is based on Jones's quadratic tangles techniques, although we apply it in a novel way. The other two are based on connections techniques; one due to Ocneanu, and the other previously unpublished, although likely known to Haagerup.We then apply these obstructions to the classification of subfactors with index below 5. In particular, we eliminate three of the five families of possible principal graphs called "weeds" in the classification from S. Morrison and N. Snyder, Subfactors of index
APA, Harvard, Vancouver, ISO, and other styles
23

Chauhan, Ankit, Tobias Friedrich, and Ralf Rothenberger. "Greed is Good for Deterministic Scale-Free Networks." Algorithmica 82, no. 11 (2020): 3338–89. http://dx.doi.org/10.1007/s00453-020-00729-z.

Full text
Abstract:
Abstract Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306–1325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks sat
APA, Harvard, Vancouver, ISO, and other styles
24

BEHBOODI, M., and Z. RAKEEI. "THE ANNIHILATING-IDEAL GRAPH OF COMMUTATIVE RINGS I." Journal of Algebra and Its Applications 10, no. 04 (2011): 727–39. http://dx.doi.org/10.1142/s0219498811004896.

Full text
Abstract:
Let R be a commutative ring, with 𝔸(R) its set of ideals with nonzero annihilator. In this paper and its sequel, we introduce and investigate the annihilating-ideal graph of R, denoted by 𝔸𝔾(R). It is the (undirected) graph with vertices 𝔸(R)* ≔ 𝔸(R)\{(0)}, and two distinct vertices I and J are adjacent if and only if IJ = (0). First, we study some finiteness conditions of 𝔸𝔾(R). For instance, it is shown that if R is not a domain, then 𝔸𝔾(R) has ascending chain condition (respectively, descending chain condition) on vertices if and only if R is Noetherian (respectively, Artinian). Moreover, t
APA, Harvard, Vancouver, ISO, and other styles
25

Gu, Mei-Mei, Hong-Xia Yan, and Jou-Ming Chang. "A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications." Mathematics 12, no. 2 (2024): 268. http://dx.doi.org/10.3390/math12020268.

Full text
Abstract:
“Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearl
APA, Harvard, Vancouver, ISO, and other styles
26

Ma, Xintao, Liyan Dong, Yuequn Wang, Yongli Li, and Hao Zhang. "MNI: An enhanced multi-task neighborhood interaction model for recommendation on knowledge graph." PLOS ONE 16, no. 10 (2021): e0258410. http://dx.doi.org/10.1371/journal.pone.0258410.

Full text
Abstract:
To alleviate the data sparsity and cold start problems for collaborative filtering in recommendation systems, side information is usually leveraged by researchers to improve the recommendation performance. The utility of knowledge graph regards the side information as part of the graph structure and gives an explanation for recommendation results. In this paper, we propose an enhanced multi-task neighborhood interaction (MNI) model for recommendation on knowledge graphs. MNI explores not only the user-item interaction but also the neighbor-neighbor interactions, capturing a more sophisticated
APA, Harvard, Vancouver, ISO, and other styles
27

Bodwin, Greg, and Virginia Vassilevska Williams. "Better Distance Preservers and Additive Spanners." ACM Transactions on Algorithms 17, no. 4 (2021): 1–24. http://dx.doi.org/10.1145/3490147.

Full text
Abstract:
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power
APA, Harvard, Vancouver, ISO, and other styles
28

Bodwin, Greg, and Virginia Vassilevska Williams. "Better Distance Preservers and Additive Spanners." ACM Transactions on Algorithms 17, no. 4 (2021): 1–24. http://dx.doi.org/10.1145/3490147.

Full text
Abstract:
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power
APA, Harvard, Vancouver, ISO, and other styles
29

HU, XIAOLAN, YUNQING ZHANG, and YAOJUN CHEN. "A NOTE ON ALMOST BALANCED BIPARTITIONS OF A GRAPH." Bulletin of the Australian Mathematical Society 91, no. 2 (2014): 177–82. http://dx.doi.org/10.1017/s0004972714000781.

Full text
Abstract:
AbstractLet $G$ be a graph of order $n\geq 6$ with minimum degree ${\it\delta}(G)\geq 4$. Arkin and Hassin [‘Graph partitions with minimum degree constraints’, Discrete Math. 190 (1998), 55–65] conjectured that there exists a bipartition $S,T$ of $V(G)$ such that $\lfloor n/2\rfloor -2\leq |S|,|T|\leq \lceil n/2\rceil +2$ and the minimum degrees in the subgraphs induced by $S$ and $T$ are at least two. In this paper, we first show that $G$ has a bipartition such that the minimum degree in each part is at least two, and then prove that the conjecture is true if the complement of $G$ contains no
APA, Harvard, Vancouver, ISO, and other styles
30

Alcon, Liliana, Luerbio Faria, Celina Figueiredo, et al. "Canonical cuts of path powers." Contributions to Discrete Mathematics 19, no. 3 (2024): 121–36. http://dx.doi.org/10.55016/ojs/cdm.v19i3.72392.

Full text
Abstract:
The MaxCut problem aims to find a bipartition of vertices in a given graph such that the number of edges with one end vertex in each part is maximum among all bipartitions. NP-hardness when restricted to interval graphs has been recently announced. Surprisingly, all previously published attempts at polynomial-time algorithms for unit interval graphs turned out to be wrong, which justifies the search for subclasses where MaxCut can be handled. We introduce canonical cuts whose pattern allows an easy computation of the cut size for the power of paths $P_n^k$. Using canonical cuts, we calculate t
APA, Harvard, Vancouver, ISO, and other styles
31

Koponen, Vera. "A Limit Law of Almost l-partite Graphs." Journal of Symbolic Logic 78, no. 3 (2013): 911–36. http://dx.doi.org/10.2178/jsl.7803110.

Full text
Abstract:
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() d
APA, Harvard, Vancouver, ISO, and other styles
32

N., Kamalraj. "Artificial Bee Colony Based Multiview Clustering ABC MVC for Graph Structure Fusion in Benchmark Datasets." International Journal of Trend in Scientific Research and Development 4, no. 2 (2020): 969–674. https://doi.org/10.5281/zenodo.3843243.

Full text
Abstract:
Combining data from several information sources has become a significant research area in classification by several scientific applications. Many of the recent work make use of kernels or graphs in order to combine varied categories of features, which normally presume one weight for one category of features. These algorithms don't consider the correlation of graph structure between multiple views, and the clustering results highly based on the value of predefined affinity graphs. Artificial Bee Colony is combined to Multi view Clustering ABC MVC model in order to combine each and every one
APA, Harvard, Vancouver, ISO, and other styles
33

Baloda, Barkha, Praveen Mathil, Jitender Kumar, and Aryan Barapatre. "Wiener index of the cozero-divisor graph of a finite commutative ring." Filomat 38, no. 17 (2024): 6259–70. https://doi.org/10.2298/fil2417259b.

Full text
Abstract:
Let R be a ring with unity. The cozero-divisor graph ??(R) of a ring R is an undirected simple graph whose vertices are the set of all non-zero and non-unit elements of R, and two distinct vertices x and y are adjacent if and only if x ? Ry and y ? Rx. To extend the corresponding results of the ring Zn of integer modulo n, in this article, we derive a closed-form formula of the Wiener index of the cozero-divisor graph of a finite commutative ring R. As applications, we compute the Wiener index of ??(R), when either R is the product of ring of integers modulo n or a reduced ring. At the final p
APA, Harvard, Vancouver, ISO, and other styles
34

Povh, Janez. "On the Embed and Project Algorithm for the Graph Bandwidth Problem." Mathematics 9, no. 17 (2021): 2030. http://dx.doi.org/10.3390/math9172030.

Full text
Abstract:
The graph bandwidth problem, where one looks for a labeling of graph vertices that gives the minimum difference between the labels over all edges, is a classical NP-hard problem that has drawn a lot of attention in recent decades. In this paper, we focus on the so-called Embed and Project Algorithm (EPA) introduced by Blum et al. in 2000, which in the main part has to solve a semidefinite programming relaxation with exponentially many linear constraints. We present several theoretical properties of this special semidefinite programming problem (SDP) and a cutting-plane-like algorithm to solve
APA, Harvard, Vancouver, ISO, and other styles
35

Planat, M., and M. Saniga. "On the Pauli graphs on N-qudits." Quantum Information and Computation 8, no. 1&2 (2008): 127–46. http://dx.doi.org/10.26421/qic8.1-2-9.

Full text
Abstract:
A comprehensive graph theoretical and finite geometrical study of the commutation relations between the generalized Pauli operators of $N$-qudits is performed in which vertices/points correspond to the operators and edges/lines join commuting pairs of them. As per two-qubits, all basic properties and partitionings of the corresponding {\it Pauli graph} are embodied in the geometry of the generalized quadrangle of order two. Here, one identifies the operators with the points of the quadrangle and groups of maximally commuting subsets of the operators with the lines of the quadrangle. The three
APA, Harvard, Vancouver, ISO, and other styles
36

Vishnupriya, R., J. Suresh, S. Sivakumar, and R. Ranjith Kumar. "N—H...O and N—H...N interactions in three pyran derivatives." Acta Crystallographica Section C Crystal Structure Communications 69, no. 6 (2013): 642–46. http://dx.doi.org/10.1107/s0108270113010676.

Full text
Abstract:
The three pyran structures 6-methylamino-5-nitro-2,4-diphenyl-4H-pyran-3-carbonitrile, C19H15N3O3, (I), 4-(3-fluorophenyl)-6-methylamino-5-nitro-2-phenyl-4H-pyran-3-carbonitrile, C19H14FN3O3, (II), and 4-(4-chlorophenyl)-6-methylamino-5-nitro-2-phenyl-4H-pyran-3-carbonitrile, C19H14ClN3O3, (III), differ in the nature of the aryl group at the 4-position. The heterocyclic ring in all three structures adopts a flattened boat conformation. The dihedral angle between the pseudo-axial phenyl substituent and the flat part of the pyran ring is 89.97 (1)° in (I), 80.11 (1)° in (II) and 87.77 (1)° in (I
APA, Harvard, Vancouver, ISO, and other styles
37

McMains, Sara, and Xiaorui Chen. "Finding Undercut-Free Parting Directions for Polygons with Curved Edges." Journal of Computing and Information Science in Engineering 6, no. 1 (2005): 60–68. http://dx.doi.org/10.1115/1.2164450.

Full text
Abstract:
We consider the problem of whether a given geometry can be molded in a two-part, rigid, reusable mold with opposite removal directions. We describe an efficient algorithm for solving the opposite direction moldability problem for a 2D “polygon” bounded by edges that may be either straight or curved. We introduce a structure, the normal graph of the polygon, that represents the range of normals of the polygon’s edges, along with their connectivity. We prove that the normal graph captures the directions of all lines corresponding to feasible parting directions. Rather than building the full norm
APA, Harvard, Vancouver, ISO, and other styles
38

Marx, Dániel, and Michał Pilipczuk. "Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams." ACM Transactions on Algorithms 18, no. 2 (2022): 1–64. http://dx.doi.org/10.1145/3483425.

Full text
Abstract:
We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O (√ k ) time brute force algorithm of selecting k objects can be improved to n O (√ k ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram
APA, Harvard, Vancouver, ISO, and other styles
39

Marjai, Péter, Bence Szabari, and Attila Kiss. "An Experimental Study on Centrality Measures Using Clustering." Computers 10, no. 9 (2021): 115. http://dx.doi.org/10.3390/computers10090115.

Full text
Abstract:
Graphs can be found in almost every part of modern life: social networks, road networks, biology, and so on. Finding the most important node is a vital issue. Up to this date, numerous centrality measures were proposed to address this problem; however, each has its drawbacks, for example, not scaling well on large graphs. In this paper, we investigate the ranking efficiency and the execution time of a method that uses graph clustering to reduce the time that is needed to define the vital nodes. With graph clustering, the neighboring nodes representing communities are selected into groups. Thes
APA, Harvard, Vancouver, ISO, and other styles
40

González A, G., and R. Galindo. "Steady state determination using bond graphs for systems with singular state matrix." Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 225, no. 7 (2011): 887–901. http://dx.doi.org/10.1177/2041304110394552.

Full text
Abstract:
A bond graph procedure to get the steady state value for linear time-invariant systems is presented. The general case of a singular state matrix is considered. The procedure is based on a junction structure configuration with derivative causality assignment, and on relationships of the bond graphs with integral and derivative causality assignments. It is shown that the structurally null modes, i.e. the poles at the origin, are cancelled for steady state. The key to cancel the poles at the origin is that the adjugate matrix of sIn − Ap multiplies Bp yielding the zeros at the origin with the sam
APA, Harvard, Vancouver, ISO, and other styles
41

Devillers, Raymond, and Ronny Tredup. "Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues." Fundamenta Informaticae 187, no. 2-4 (2022): 139–65. http://dx.doi.org/10.3233/fi-222135.

Full text
Abstract:
Petri net synthesis consists in deciding for a given transition system A whether there exists a Petri net N whose reachability graph is isomorphic to A. Several works examined the synthesis of Petri net subclasses that restrict, for every place p of the net, the cardinality of its preset or of its postset or both in advance by small natural numbers ϱ and κ, respectively, such as for example (weighted) marked graphs, (weighted) T-systems and choice-free nets. In this paper, we study the synthesis aiming at Petri nets which have such restricted place environments, from the viewpoint of classical
APA, Harvard, Vancouver, ISO, and other styles
42

Bringmann, Karl, Marvin KüNnemann, and André Nusser. "Discrete Fréchet Distance under Translation." ACM Transactions on Algorithms 17, no. 3 (2021): 1–42. http://dx.doi.org/10.1145/3460656.

Full text
Abstract:
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length n in the plane, the fastest known algorithm runs in time Õ( n 5 ) [12]. This is achieved by constructing an arrangement of disks of size Õ( n 4 ), and then traversing its faces while updating reachability in a directed grid graph of size N := Õ( n 5 ), which can be done in time Õ(√ N ) per update [27]. The contribution of this a
APA, Harvard, Vancouver, ISO, and other styles
43

Potůček, Radovan. "The Number of Fillings a 2×2×n prism with 1×1×2 prisms." EQUATIONS 3 (October 3, 2023): 104–14. http://dx.doi.org/10.37394/232021.2023.3.12.

Full text
Abstract:
This paper is inspired by very interesting YouTube video of Burkard Polster, professor of mathematics at Monash University in Melbourne, Australia, which, among other things, concerned the number of ways to fill a part of the plane with dominoes, i.e. 1×2 rectangles. First we deal with the numbers of fillings the 2×2×n prism with elementary 1×1×2 prisms for n=1,2,3,4,5. Special symbolism and figures showing the filling of the prism are used as well as the concept of matching from graph theory and the corresponding graph diagrams. Then we generalize these specific considerations and derive a ge
APA, Harvard, Vancouver, ISO, and other styles
44

CHAUDHURI, SUTAPA. "CHAOTIC GRAPH THEORY APPROACH FOR IDENTIFICATION OF CONVECTIVE AVAILABLE POTENTIAL ENERGY (CAPE) PATTERNS REQUIRED FOR THE GENESIS OF SEVERE THUNDERSTORMS." Advances in Complex Systems 10, no. 03 (2007): 413–22. http://dx.doi.org/10.1142/s0219525907001215.

Full text
Abstract:
Severe thunderstorms are a manifestation of deep convection. Conditional instability is known to be the mechanism by which thunderstorms are formed. The energy that drives conditional instability is convective available potential energy (CAPE), which is computed with radio sonde data at each pressure level. The purpose of the present paper is to identify the pattern or shape of CAPE required for the genesis of severe thunderstorms over Kolkata (22°32′N, 88°20′E) confined within the northeastern part (20°N to 24°N latitude, 85°E to 93°E longitude) of India. The method of chaotic graph theory is
APA, Harvard, Vancouver, ISO, and other styles
45

Li, Shiqiao, and Jami J. Shah. "Recognition of User-Defined Turning Features for Mill/Turn Parts." Journal of Computing and Information Science in Engineering 7, no. 3 (2007): 225–35. http://dx.doi.org/10.1115/1.2767256.

Full text
Abstract:
This paper focuses on efficient algorithms for automatic recognition of user-defined turning features on mill/turn parts. As with other domains, recognition of interacting features is a difficult issue because feature interaction removes faces and alters the topology of the isolated turning features. This paper presents a method for efficiently recognizing both noninteracting and interacting rotational features from CAD model of mill/turn parts. Additionally, the method supports user-defined turning features that are represented using N-REP, a neutral feature representation language. First, th
APA, Harvard, Vancouver, ISO, and other styles
46

MATIGNON, DANIEL. "COMBINATORICS AND FOUR BRIDGED KNOTS." Journal of Knot Theory and Its Ramifications 10, no. 04 (2001): 493–527. http://dx.doi.org/10.1142/s0218216501000974.

Full text
Abstract:
The ℝ P 3-Conjecture states a non-trivial knot in S 3 cannot yield ℝ P 3 by a Dehn surgery. Generically, in the knot-space S3-N(K), the intersection of a projective plane ℝP2 in ℝ P 3, and any 2-sphere S2 in S3 pierced by K, is a 1-complex which can be viewed as a graph in either the projective plane or the 2-sphere. Gordon and Luecke have used similar graphs arising as the intersection of two 2-spheres, to prove that a knot in S3 is determined by its complement. A part of this paper concerns some new combinatorial results on these graphs. They are considered as an unavoidable step towards sho
APA, Harvard, Vancouver, ISO, and other styles
47

Nichol, Gary S., Jamie M. Frost, Sergio Sanz, and Euan K. Brechin. "Crystal structure of 2-hydroxy-N-(2-hydroxyethyl)-N-{2-hydroxy-3-[(E)-N-hydroxyethanimidoyl]-5-methylbenzyl}ethanaminium acetate monohydrate." Acta Crystallographica Section E Crystallographic Communications 71, no. 3 (2015): o186—o187. http://dx.doi.org/10.1107/s2056989015002418.

Full text
Abstract:
The structure of the title hydrated molecular salt, C14H23N2O4+·C2H3O2−·H2O, was determined as part of a wider study on the use of the molecule as a polydentate ligand in the synthesis of MnIIIclusters with magnetic properties. The cation features intramolecular O—H...N and N—H...O hydrogen-bond interactions. The crystal structure features a range of intermolecular hydrogen-bonding interactions, principally O—H...O interactions between all three species in the asymmetric unit. AnR24(8) graph-set hydrogen-bonding motif between the anion and water molecules serves as a unit which links to the ca
APA, Harvard, Vancouver, ISO, and other styles
48

Hu, Zhichao, Likun Liu, Haining Yu, and Xiangzhan Yu. "Using Graph Representation in Host-Based Intrusion Detection." Security and Communication Networks 2021 (December 7, 2021): 1–13. http://dx.doi.org/10.1155/2021/6291276.

Full text
Abstract:
Cybersecurity has become an important part of our daily lives. As an important part, there are many researches on intrusion detection based on host system call in recent years. Compared to sentences, a sequence of system calls has unique characteristics. It contains implicit pattern relationships that are less sensitive to the order of occurrence and that have less impact on the classification results when the frequency of system calls varies slightly. There are also various properties such as resource consumption, execution time, predefined rules, and empirical weights of system calls. Common
APA, Harvard, Vancouver, ISO, and other styles
49

Shekhawat, Krishnendra, and José P. Duarte. "Introduction to generic rectangular floor plans." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 32, no. 3 (2018): 331–50. http://dx.doi.org/10.1017/s0890060417000671.

Full text
Abstract:
AbstractAn important task in the initial stages of most architectural design processes is the design of planar floor plans, that are composed of non-overlapping rooms divided from each other by walls while satisfying given topological and dimensional constraints. The work described in this paper is part of a larger research aimed at developing the mathematical theory for examining the feasibility of given topological constraints and providing a generic floor plan solution for all possible design briefs.In this paper, we mathematically describe universal (or generic) rectangular floor plans wit
APA, Harvard, Vancouver, ISO, and other styles
50

Ganesan, Ghurumuruhan. "Infection Spread in Random Geometric Graphs." Advances in Applied Probability 47, no. 01 (2015): 164–81. http://dx.doi.org/10.1017/s0001867800007758.

Full text
Abstract:
In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G(n, r n , f) of n nodes independently distributed in S = [-½, ½]2 according to a certain density f(·). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D 1 nr n 2. In the second part of the paper we consider the contact process ξ t on G
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!

To the bibliography