5,390 results on '"Graph"'
Search Results
2. Development of message passing-based graph convolutional networks for classifying cancer pathology reports.
- Author
-
Yoon, Hong-Jun, Klasky, Hilda B., Blanchard, Andrew E., Christian, J. Blair, Durbin, Eric B., Wu, Xiao-Cheng, Stroup, Antoinette, Doherty, Jennifer, Coyle, Linda, Penberthy, Lynne, and Tourassi, Georgia D.
- Subjects
- *
CONVOLUTIONAL neural networks , *NATURAL language processing , *DATA mining , *TASK performance , *DEEP learning - Abstract
Background: Applying graph convolutional networks (GCN) to the classification of free-form natural language texts leveraged by graph-of-words features (TextGCN) was studied and confirmed to be an effective means of describing complex natural language texts. However, the text classification models based on the TextGCN possess weaknesses in terms of memory consumption and model dissemination and distribution. In this paper, we present a fast message passing network (FastMPN), implementing a GCN with message passing architecture that provides versatility and flexibility by allowing trainable node embedding and edge weights, helping the GCN model find the better solution. We applied the FastMPN model to the task of clinical information extraction from cancer pathology reports, extracting the following six properties: main site, subsite, laterality, histology, behavior, and grade. Results: We evaluated the clinical task performance of the FastMPN models in terms of micro- and macro-averaged F1 scores. A comparison was performed with the multi-task convolutional neural network (MT-CNN) model. Results show that the FastMPN model is equivalent to or better than the MT-CNN. Conclusions: Our implementation revealed that our FastMPN model, which is based on the PyTorch platform, can train a large corpus (667,290 training samples) with 202,373 unique words in less than 3 minutes per epoch using one NVIDIA V100 hardware accelerator. Our experiments demonstrated that using this implementation, the clinical task performance scores of information extraction related to tumors from cancer pathology reports were highly competitive. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Remarks on restricted fractional [formula omitted]-factors in graphs.
- Author
-
Zhou, Sizhong
- Subjects
- *
INDEPENDENT sets , *SPANNING trees - Abstract
Assume there exists a function h : E (G) → [ 0 , 1 ] such that g (x) ≤ ∑ e ∈ E (G) , x ∋ e h (e) ≤ f (x) for every vertex x of G. The spanning subgraph of G induced by the set of edges { e ∈ E (G) : h (e) > 0 } is called a fractional (g , f) -factor of G with indicator function h. Let M and N be two disjoint sets of independent edges of G satisfying | M | = m and | N | = n. We say that G possesses a fractional (g , f) -factor with the property E (m , n) if G contains a fractional (g , f) -factor with indicator function h such that h (e) = 1 for each e ∈ M and h (e) = 0 for each e ∈ N. In this article, we discuss stability number and minimum degree conditions for graphs to possess fractional (g , f) -factors with the property E (1 , n). Furthermore, we explain that the stability number and minimum degree conditions declared in the main result are sharp. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. A generalization of the cozero-divisor graph of a commutative ring.
- Author
-
Farshadifar, F.
- Subjects
- *
COMPLETE graphs , *GRAPH connectivity , *GENERALIZATION , *DIVISOR theory - Abstract
Let R be a commutative ring with identity and I be an ideal of R. The zero-divisor graph of R with respect to I, denoted by ΓI(R), is the graph whose vertices are the set {x ∈ R∖I|xy ∈ I for some y ∈ R∖I} with distinct vertices x and y are adjacent if and only if xy ∈ I. The cozero-divisor graph Γ′(R) of R is the graph whose vertices are precisely the non-zero, non-unit elements of R and two distinct vertices x and y are adjacent if and only if x∉yR and y∉xR. In this paper, we introduced and investigated a new generalization of the cozero-divisor graph Γ′(R) of R denoted by ΓI″(R). In fact, ΓI″(R) is a dual notion of ΓI(R). [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
5. Moran's I for Multivariate Spatial Data.
- Author
-
Yamada, Hiroshi
- Subjects
- *
JOB applications - Abstract
Moran's I is a spatial autocorrelation measure of univariate spatial data. Therefore, even if p spatial data exist, we can only obtain p values for Moran's I. In other words, Moran's I cannot measure the degree of spatial autocorrelation of multivariate spatial data as a single value. This paper addresses this issue. That is, we extend Moran's I so that it can measure the degree of spatial autocorrelation of multivariate spatial data as a single value. In addition, since the local version of Moran's I has the same problem, we extend it as well. Then, we establish their properties, which are fundamental for applied work. Numerical illustrations of the theoretical results obtained in the paper are also provided. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
6. Simplified algorithms for order-based core maintenance.
- Author
-
Guo, Bin and Sekerinski, Emil
- Subjects
- *
TIME complexity , *ALGORITHMS , *SOCIAL networks , *DATA structures - Abstract
Graph analytics attract much attention from both research and industry communities. Due to its linear time complexity, the k-core decomposition is widely used in many real-world applications such as biology, social networks, community detection, ecology, and information spreading. In many such applications, the data graphs continuously change over time. The changes correspond to edge insertion and removal. Instead of recomputing the k-core, which is time-consuming, we study how to maintain the k-core efficiently. That is, when inserting or deleting an edge, we need to identify the affected vertices by searching for more vertices. The state-of-the-art order-based method maintains an order, the so-called k-order, among all vertices, which can significantly reduce the searching space. However, this order-based method is complicated to understand and implement, and its correctness is not formally discussed. In this work, we propose a simplified order-based approach by introducing the classical Order Data Structure to maintain the k-order, which significantly improves the worst-case time complexity for both edge insertion and removal algorithms. Also, our simplified method is intuitive to understand and implement; it is easy to argue the correctness formally. Additionally, we discuss a simplified batch insertion approach. The experiments evaluate our simplified method over 12 real and synthetic graphs with billions of vertices. Compared with the existing method, our simplified approach achieves high speedups up to 7.7× and 9.7× for edge insertion and removal, respectively. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. Optimal coverage of borders using unmanned aerial vehicles.
- Author
-
Etezadi, Mohammad, Ashrafi, Siamak, and Ghasemi, Mostafa
- Subjects
- *
DRONE aircraft , *FUEL costs , *EMERGENCIES , *FLIGHT - Abstract
Unmanned Aerial Vehicles (UAVs) play a very important role in military and civilian activities. In this paper, the aim is to cover the borders of Iran using UAVs. For this purpose, two zero-one programming models are presented. In the first model, our goal is to cover the borders of Iran at the minimum total time (the required time to prepare UAVs to start flying and the flight time of the UAVs). In this model, by minimizing the total time of UAVs for covering the borders, the costs appropriate to the flight of UAVs (such as the fuel costs of UAVs) are also reduced. In the second model, which is mostly used in emergencies and when a military attack occurs on the country’s borders, the aim is to minimize the maximum required time to counter attacks and cover the entire country’s borders. The efficiency of both models is shown by numerical examples. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. On the Extremal Values of the Weighted Integrity of a Graph.
- Author
-
Goddard, Wayne and VanLandingham, Julia
- Subjects
- *
WEIGHTED graphs - Abstract
The integrity of a graph G is defined as the minimum value of | S | + m (G − S) taken over all S ⊆ V (G) , where m (H) denotes the maximum cardinality of a component of graph H. In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
9. Local degree conditions for K9 ${K}_{9}$‐minors in graphs.
- Author
-
Akiyama, Takashige
- Subjects
- *
LOGICAL prediction , *TRIANGLES , *MINORS , *MATROIDS - Abstract
We prove that if each edge of a graph G $G$ belongs to at least seven triangles, then G $G$ contains a K9 ${K}_{9}$‐minor or contains K1,2,2,2,2,2 ${K}_{1,2,2,2,2,2}$ as an induced subgraph. This result was conjectured by Albar and Gonçalves in 2018. Moreover, we apply this result to study the stress freeness of graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
10. Hausdorff Measure and Uniform Dimension for Space-Time Anisotropic Gaussian Random Fields.
- Author
-
Yuan, Weijie and Chen, Zhenlong
- Abstract
Let X = { X (t) , t ∈ R N } be a centered space-time anisotropic Gaussian random field in R d with stationary increments, where the components X i (i = 1 , ... , d) are independent but distributed differently. Under certain conditions, we not only give the Hausdorff dimension of the graph sets of X in the asymmetric metric in the recurrent case, but also determine the exact Hausdorff measure functions of the graph sets of X in the transient and recurrent cases, respectively. Moreover, we establish a uniform Hausdorff dimension result for the image sets of X. Our results extend the corresponding results on fractional Brownian motion and space or time anisotropic Gaussian random fields. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
11. Parallelization of butterfly counting on hierarchical memory.
- Author
-
Wang, Zhibin, Lai, Longbin, Liu, Yixue, Shui, Bing, Tian, Chen, and Zhong, Sheng
- Abstract
Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of this kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ω ( | E | 2 MB) of a witnessing algorithm, and give a new bound of Ω (min ( | E | 2 MB , | E | | V | M B)) . Subsequently, we develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we investigate the parallelization of IOBufs to improve its performance and scalability. To support various hardware configurations, we introduce a general parallel framework, PIOBufs . Our analysis indicates that the key to implementing PIOBufs on multi-core CPUs lies in the fine-grained task division. Furthermore, we extend the CPU-tailored PIOBufs to harness the extensive parallelism that GPUs provide. Our experimental results show that IOBufs performs better than established algorithms such as EMRC , BFC - EM and G - BFC . Thanks to its I/O-efficient design, IOBufs can handle large graphs that exceed the main memory capacity on both CPUs and GPUs. A significant result is that IOBufs can manage butterfly counting on the Clueweb graph, which has 37 billion edges and quintillions ( 10 18 ) of butterflies. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
12. Tight isolated toughness bound for fractional (a,b,m)-deleted graphs.
- Author
-
Gao, Wei, Wang, Weifan, and Chen, Yaojun
- Subjects
- *
TOPOLOGY , *MEASUREMENT - Abstract
A graph G is a fractional (a,b,m)-deleted graph if deleting any m edges from G, the resulting subgraph still admits a fractional [a,b]-factor. As an exclusive graph-based parameter, isolated toughness and its variant are utilized to measure the vulnerability of networks which are modelled by graph topology structures. Early studies have shown the inherent connection between isolated toughness and the existence of fractional factors in specific settings. This paper provides a theoretical perspective on the sufficient conditions for fractional (a,b,m)-deleted graphs with respect to isolated toughness and its variant. The sharpness of the given isolated toughness bounds is explained by counterexamples. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
13. A Bellman–Ford Algorithm for the Path-Length-Weighted Distance in Graphs.
- Author
-
Arnau, Roger, Calabuig, José M., García-Raffi, Luis M., Sánchez Pérez, Enrique A., and Sanjuan, Sergi
- Subjects
- *
FRAUD investigation , *DIRECTED graphs , *GRAPH algorithms , *FRAUD , *INTERMEDIATION (Finance) , *WEIGHTED graphs - Abstract
Consider a finite directed graph without cycles in which the arrows are weighted by positive weights. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection. The idea is that the new distance explicitly takes into account the size of the paths in the calculations. It has the distinct characteristic that, when calculated along the same path, it may result in a shorter distance between far-apart vertices than between adjacent ones. This property can be particularly useful for modeling scenarios where the connections between vertices are obscured by numerous intermediate vertices, such as in cases of financial fraud. For example, to hide dirty money from financial authorities, fraudsters often use multiple institutions, banks, and intermediaries between the source of the money and its final recipient. Our distance would serve to make such situations explicit. Thus, although our algorithm is based on arguments similar to those at work for the Bellman–Ford and Dijkstra methods, it is in fact essentially different, since the calculation formula contains a weight that explicitly depends on the number of intermediate vertices. This fact totally conditions the algorithm, because longer paths could provide shorter distances—contrary to the classical algorithms mentioned above. We lay out the appropriate framework for its computation, showing the constraints and requirements for its use, along with some illustrative examples. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
14. Human adolescent brain similarity development is different for paralimbic versus neocortical zones.
- Author
-
Dorfschmidt, Lena, Váša, František, White, Simon R., Romero-García, Rafael, Kitzbichler, Manfred G., Alexander-Bloch, Aaron, Cieslak, Matthew, Mehta, Kahini, Satterthwaite, Theodore D., Bethlehem, Richard A. I., Seidlitz, Jakob, Vértes, Petra E., and Bullmore, Edward T.
- Subjects
- *
MAGNETIC resonance imaging , *FUNCTIONAL magnetic resonance imaging , *ADOLESCENT development , *CEREBRAL cortical thinning , *CINGULATE cortex - Abstract
Adolescent development of human brain structural and functional networks is increasingly recognized as fundamental to emergence of typical and atypical adult cognitive and emotional processes. We analysed multimodal magnetic resonance imaging (MRI) data collected from N ~ 300 healthy adolescents (51%; female; 14 to 26 y) each scanned repeatedly in an accelerated longitudinal design, to provide an analyzable dataset of 469 structural scans and 448 functional MRI scans. We estimated the morphometric similarity between each possible pair of 358 cortical areas on a feature vector comprising six macro- and microstructural MRI metrics, resulting in a morphometric similarity network (MSN) for each scan. Over the course of adolescence, we found that morphometric similarity increased in paralimbic cortical areas, e.g., insula and cingulate cortex, but generally decreased in neocortical areas, and these results were replicated in an independent developmental MRI cohort (N~304). Increasing hubness of paralimbic nodes in MSNs was associated with increased strength of coupling between their morphometric similarity and functional connectivity. Decreasing hubness of neocortical nodes in MSNs was associated with reduced strength of structure-function coupling and increasingly diverse functional connections in the corresponding fMRI networks. Neocortical areas became more structurally differentiated and more functionally integrative in a metabolically expensive process linked to cortical thinning and myelination, whereas paralimbic areas specialized for affective and interoceptive functions became less differentiated, as hypothetically predicted by a developmental transition from periallocortical to proisocortical organization of the cortex. Cytoarchitectonically distinct zones of the human cortex undergo distinct neurodevelopmental programs during typical adolescence. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
15. THE GRAPH THEORETIC FORMULATION OF THE TEAM FORMATION PROBLEM BASED ON THE FACTOR OF COMPETITION.
- Author
-
Ryabenko, Anton, Tereschenko, Elina, Bakurova, Anna, Pyrozhok, Andrii, and Kuzkin, Olexiy
- Subjects
- *
PARETO optimum , *MATHEMATICAL models , *WEIGHTED graphs , *ADMISSIBLE sets , *UNDIRECTED graphs - Abstract
The object of the research is to increase the level of productivity of teamwork due to the effective selection of participants who demonstrate the highest level of productivity in cooperation. The presented research is aimed at the mathematical formalization of the problem of team formation based on the results of a series of competitions using graph-theoretic approaches. Each competition in this series involves teams with the same number of participants. The composition of the team necessarily changes for each subsequent competition. After the competitive series, the obtained information about the teams’ composition and their results is evaluated for the success of the interaction of the participants, which can be used in the formation of successful teams. A graph-theoretic formalization of the team formation problem on a complete undirected weighted graph has been developed. The set of vertices of this graph corresponds to the set of potential participants. Each edge is weighted with a number that reflects the quality of the interaction between the two participants. A valid solution is to cover the graph with cliques, the size of which is determined by the number of team members. A mathematical model of a two-criterion problem with MAXSUM and MAXMIN criteria was built, where the first criterion evaluates the overall success of the created teams, the second criterion evaluates the «weakest link», allowing to choose the option that maximizes the minimum edge weights for each clique. A two-criterion objective function defines a Pareto set consisting of all Pareto optima in the set of admissible solutions. The algorithmic problem of finding the complete set of alternatives, which is a subset of the Pareto set of minimum power when the condition of equality of the objective functions for the complete set of alternatives and the Pareto set is fulfilled, is considered. The weight of the edges of the graph is calculated using the scores obtained during the series of competitions. In practice, the research results can be used as a basis for the development of team building techniques. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
16. On Some Distance Spectral Characteristics of Trees.
- Author
-
Hayat, Sakander, Khan, Asad, and Alenazi, Mohammed J. F.
- Subjects
- *
DATA transmission systems , *LINEAR algebra , *GRAPH theory , *SPECTRAL theory , *GRAPH connectivity - Abstract
Graham and Pollack in 1971 presented applications of eigenvalues of the distance matrix in addressing problems in data communication systems. Spectral graph theory employs tools from linear algebra to retrieve the properties of a graph from the spectrum of graph-theoretic matrices. The study of graphs with "few eigenvalues" is a contemporary problem in spectral graph theory. This paper studies graphs with few distinct distance eigenvalues. After mentioning the classification of graphs with one and two distinct distance eigenvalues, we mainly focus on graphs with three distinct distance eigenvalues. Characterizing graphs with three distinct distance eigenvalues is "highly" non-trivial. In this paper, we classify all trees whose distance matrix has precisely three distinct eigenvalues. Our proof is different from earlier existing proof of the result as our proof is extendable to other similar families such as unicyclic and bicyclic graphs. The main tools which we employ include interlacing and equitable partitions. We also list all the connected graphs on ν ≤ 6 vertices and compute their distance spectra. Importantly, all these graphs on ν ≤ 6 vertices are determined from their distance spectra. We deliver a distance cospectral pair of order 7, thus making it a distance cospectral pair of the smallest order. This paper is concluded with some future directions. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
17. Converting Tessellations into Graphs: From Voronoi Tessellations to Complete Graphs.
- Author
-
Gilevich, Artem, Shoval, Shraga, Nosonovsky, Michael, Frenkel, Mark, and Bormashenko, Edward
- Subjects
- *
UNCERTAINTY (Information theory) , *VORONOI polygons , *RAMSEY theory , *COMPLETE graphs , *RANDOM graphs - Abstract
A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as R t r a n s (3 , 3) = 5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ = lim N → ∞ N g N r , where N is the total number of green and red seeds, N g and N r , were found ζ = 0.272 ± 0.001 (Voronoi) and ζ = 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S = 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
18. Cloning operations and graph diameter.
- Author
-
Iordanskiy, Mikhail A.
- Subjects
- *
GENEALOGY , *DIAMETER - Abstract
The influence of the subgraph cloning operation on the graph diameter is studied. The corresponding potential increase in the diameter is estimated. Conditions under which the subgraph cloning operation causes no change in the graph diameter are formulated. An example of using the cloning operation to construct a family of fat trees is presented. The diameter of such graphs and the complexity of their design are estimated. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
19. Newly defined fuzzy Misbalance Prodeg Index with application in multi-criteria decision-making.
- Author
-
Liaqat, Shama, Mufti, Zeeshan Saleem, and Yilun Shang
- Subjects
COMPLETE graphs ,MOLECULAR connectivity index ,GRAPH theory ,FUZZY algorithms ,EVERYDAY life ,BIPARTITE graphs ,FUZZY graphs ,FUZZY sets - Abstract
In crisp graph theory, there are numerous topological indices accessible, including the Misbalance Prodeg Index, which is one of the most well-known degree-based topological indexes. In crisp graphs, both vertices and edges have membership values of 1 or 0, whereas in fuzzy graphs, both vertices and edges have different memberships. This is an entire contrast to the crisp graph. In this paper, we introduce the Fuzzy Misbalance Prodeg Index of a fuzzy graph, which is a generalized form of the Misbalance Prodeg Index of a graph. We find bounds of this index and find bounds of certain classes of graphs such as path graph, cycle graph, complete graph, complete bipartite graph, and star graph. We give an algorithm to find the Fuzzy Misbalance Prodeg Index of a graph for the model of multi-criteria decision-making is established. We present applications from daily life in multi-criteria decision-making. We apply our obtained model of the Fuzzy Misbalance Prodeg Index for the multicriteria decision-making to the choice of the best supplier and we also show the graphical analysis of our index with the other indices that show how our index is better than other existing indices. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
20. Characterization of the absorption radical of an evolution algebra using their associated graph.
- Author
-
Cadavid, Paula, Reis, Tiago, and Montoya, Mary Luz Rodiño
- Subjects
- *
ALGEBRA , *ABSORPTION , *ACYCLIC model - Abstract
In this paper, we present a method for finding the absorbing radical of a finite-dimensional evolution algebra. Such a method consists of finding the acyclic vertices of an oriented graph associated with the algebra. The set of generators associated with such vertices turn out to be the generators of the absorption radical. As an application we use the absorption radical to study the decomposability of some degenerate evolution algebras. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
21. Investigating the impact of standard brain atlases and connectivity measures on the accuracy of ADHD detection from fMRI data using deep learning.
- Author
-
Agarwal, Snigdha, Raj, Adarsh, Chowdhury, Anjan, Aich, Geetanjali, Chatterjee, Rajdeep, and Ghosh, Kuntal
- Subjects
DEEP learning ,DEEP brain stimulation ,FUNCTIONAL magnetic resonance imaging ,ARTIFICIAL neural networks ,ATTENTION-deficit hyperactivity disorder - Abstract
Inattention, hyperactivity, and impulsivity are among the symptoms of Attention Deficit Hyperactivity Syndrome (ADHD). This brain disorder cannot currently be treated or avoided. A kid or adult with ADHD may be able to control their symptoms, though, if they are diagnosed early and have a good treatment and education plan. Functional magnetic resonance imaging (fMRI) is one of the non-invasive imaging techniques used to diagnose ADHD. The blood-oxygen-level-dependent (BOLD) signals extracted from several brain regions (obtained by choosing a brain atlas) are processed to form a brain functional connectivity matrix and fed into a deep learning model for the classification of ADHD. In this paper, we study two things: first, we diagnose the ADHD using fMRI data by proposing two approaches, viz., an image-based approach and a graph-based (network-based) approach. In the image-based approach, the connectivity matrix obtained from the fMRI data is used directly as an image, and the whole image is fed into a deep learning model. In the network-based approach, the connectivity matrix is first converted into an adjacency matrix, which represents an undirected network. After that, several network properties are accumulated as features, and the feature vector is fed into the deep learning model. Second, we study how the choice of a particular brain atlas or connectivity matrix can affect the accuracy of the ADHD diagnosis. The suggested algorithms, along with six different atlases and two different connectivity matrices, are compared using 352 fMRI images and various one- and two-dimensional neural network models. Our finding demonstrates that accuracy varies depending on the atlases and connectivity measurements used. In addition, we have shown that, with a particular setup, our algorithms outperform a number of deep-learning baselines showing the second best (ranging from 74.48% to 90.90%) results most of the time. Application of various atlases and connectivity matrices shows 64% variations in the overall accuracy. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
22. Three Existence Results in the Fixed Point Theory.
- Author
-
Zaslavski, Alexander J.
- Subjects
- *
FIXED point theory , *METRIC spaces , *SET-valued maps , *GENERALIZATION - Abstract
In the present paper, we obtain three results on the existence of a fixed point for nonexpansive mappings. Two of them are generalizations of the result for F-contraction, while third one is a generalization of a recent result for set-valued contractions. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
23. Automatic Detection of Acute Leukemia (ALL and AML) Utilizing Customized Deep Graph Convolutional Neural Networks.
- Author
-
Zare, Lida, Rahmani, Mahsan, Khaleghi, Nastaran, Sheykhivand, Sobhan, and Danishvar, Sebelan
- Subjects
- *
LYMPHOBLASTIC leukemia , *CONVOLUTIONAL neural networks , *MACHINE learning , *ACUTE leukemia , *ACUTE myeloid leukemia - Abstract
Leukemia is a malignant disease that impacts explicitly the blood cells, leading to life-threatening infections and premature mortality. State-of-the-art machine-enabled technologies and sophisticated deep learning algorithms can assist clinicians in early-stage disease diagnosis. This study introduces an advanced end-to-end approach for the automated diagnosis of acute leukemia classes acute lymphocytic leukemia (ALL) and acute myeloid leukemia (AML). This study gathered a complete database of 44 patients, comprising 670 ALL and AML images. The proposed deep model's architecture consisted of a fusion of graph theory and convolutional neural network (CNN), with six graph Conv layers and a Softmax layer. The proposed deep model achieved a classification accuracy of 99% and a kappa coefficient of 0.85 for ALL and AML classes. The suggested model was assessed in noisy conditions and demonstrated strong resilience. Specifically, the model's accuracy remained above 90%, even at a signal-to-noise ratio (SNR) of 0 dB. The proposed approach was evaluated against contemporary methodologies and research, demonstrating encouraging outcomes. According to this, the suggested deep model can serve as a tool for clinicians to identify specific forms of acute leukemia. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
24. Cohesive powers of structures.
- Author
-
Harizanov, Valentina and Srinivasan, Keshav
- Subjects
- *
COMPUTABLE functions , *DIRECTED graphs , *NATURAL numbers , *ISOMORPHISM (Mathematics) - Abstract
A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the cohesive set. Thus, unlike many classical ultrapowers, a cohesive power is a countable structure. In this paper we focus on cohesive powers of graphs, equivalence structures, and computable structures with a single unary function satisfying various properties, which can also be viewed as directed graphs. For these computable structures, we investigate the isomorphism types of their cohesive powers, as well as the properties of cohesive powers when they are not isomorphic to the original structure. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
25. The crossing numbers of join product of four graphs on six vertices with discrete graphs.
- Author
-
Staš, Michal
- Subjects
- *
GEOMETRIC vertices , *GRAPH theory , *EXISTENCE theorems , *ISOMORPHISM (Mathematics) , *SUBGRAPHS - Abstract
The main aim of the paper is to give the crossing number of the join product G* + Dn for the graph G* isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where Dn consists of n isolated vertices. The proofs are done with possibility of an existence of a separating cycle in some particular drawing of the investigated graph G* and also with the help of well-known exact values for crossing numbers of join products of two subgraphs Hk of G* with discrete graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
26. The implementation of deep clustering for SuperDARN backscatter echoes.
- Author
-
Kong, Xing, Liu, Erxiao, Shi, Shengsheng, and Chen, Fengjv
- Subjects
- *
BACKSCATTERING , *MACHINE learning , *SPACE environment , *METEOROLOGICAL research , *CLUSTER analysis (Statistics) - Abstract
The collection of SuperDARN ionospheric echo data to make ionospheric convection maps is of great significance for Space Weather research. The ionospheric echoes for SuperDARN are generally mixed with scatter from the ground or sea surface, thus the clustering analysis of SuperDARN backscatter echoes is important. In this paper, the first implementation of deep clustering based on the graph automatic encoder network is efficiently realized for classifying the SuperDARN data. In addition, the model is compared with the traditional algorithm and machine learning clustering algorithms. Application of the model to sample data reveals that the deep clustering algorithm can capture the structural characteristics of the echoes and improve the accuracy of echo clustering and classifying. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
27. Fractional Matchings in Graphs from the Spectral Radius.
- Author
-
Chen, Qian-Qian, Guo, Ji-Ming, and Wang, Zhiwen
- Abstract
Denote by G n , ν ∗ (G n , ν ∗ ∗) the collection of all (connected) graphs of order n having a fractional matching number ν ∗ . This paper characterizes the graphs in G n , ν ∗ and G n , ν ∗ ∗ with the maximum spectral radius, and establishes a lower bound for the spectral radius of graphs of order n to guarantee that their fractional matching numbers are at least τ + 1 2 . In addition, we explore the relationship between the spectral radius, perfect matching and fractional perfect matching of G. Moreover, we present a spectral condition guaranteeing that the matching number of a graph is at least k + 1 , which generalizes some previous known results. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
28. A spectral condition for component factors in graphs.
- Author
-
Wang, Sufang and Zhang, Wei
- Abstract
Let G be a graph. A {K
1,2 , K1,3 , K5 }-factor of G is a spanning subgraph of G, in which every component is isomorphic to a member of {K1,2 , K1,3 , K5 }. In this paper, we establish a lower bound on the spectral radius of G to ensure that G contains a {K1,2 , K1,3 , K5 }-factor. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
29. 실내 차량 측위를 위한 그래프기반 딥러닝 모델 분석.
- Author
-
최영록, 나정효, and 박판근
- Subjects
LOCATION data ,DIRECTED graphs ,ACQUISITION of data ,DEEP learning ,VEHICLE models ,DATA quality - Abstract
While the quality and quantity of data directly impact the estimation accuracy of deep learning-based localization technology, collecting empirical location data in large-scale indoor environments consumes significant time and resources. This paper proposes a novel training and data collection method for constructing a deep learning-based localization model for indoor vehicle localization using multi-directional beacons. We first develop different deep learning-based localization models and then define a directed graph to analyze the model applicability. We deploy the large number of multi-directional beacons to evaluate the proposed scheme and run extensive set of experiments to obtain the training data in the indoor testbed. The performance evaluation shows that the proposed deep learning-based localization model provides fairly good estimation accuracy. Furthermore, the directed graph demonstrates that the location labeling data of beacons can be significantly reduced while providing good estimation accuracy for the indoor scenario. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
30. A k-IDEAL-BASED GRAPH OF COMMUTATIVE SEMIRINGS.
- Author
-
KHALIL SARAEI, F. ESMAEILI and RAMINFAR, S.
- Subjects
COMMUTATIVE rings ,COHOMOLOGY theory ,SEMIGROUPS (Algebra) ,MODULES (Algebra) ,SEMIRINGS (Mathematics) - Abstract
Let R be a commutative semiring and I be a k-ideal of R. In this paper, we introduce the k-ideal-based graph of R, denoted by Γ
I ∗ (R). The basic properties and possible structures of the graph are studied. [ABSTRACT FROM AUTHOR]- Published
- 2024
31. Periodic and fixed points for mappings in extended b-gauge spaces equipped with a graph
- Author
-
Zikria Nosheen, Samreen Maria, Savas Ekrem, Sen Manuel De la, and Kamran Tayyab
- Subjects
generalized extended pseudo-b-distances ,g-contraction ,alpha-contraction ,extended b-gauge space ,fixed point ,periodic point ,graph ,47h10 ,54h25 ,Mathematics ,QA1-939 - Abstract
This article presents the notions of extended b-gauge space (U,Qφ;Ω)\left(U,{Q}_{\varphi ;\Omega }) and extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-families of generalized extended pseudo-b-distances on UU. Furthermore, we look at these extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-families on UU and define the extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-sequential completeness. We also look into some fixed and periodic point theorems for set-valued mappings in the new space with a graph that does not meet the completeness condition of the space. Additionally, this article includes some examples to explain the corresponding results and highlights some important consequences of our obtained results.
- Published
- 2024
- Full Text
- View/download PDF
32. On curve fitting between topological indices and Gibb’s energy for semiconducting carbon nitrides network
- Author
-
Rongbing Huang, Maged Z. Youssef, Ibrahim Al-Dayel, Muhammad Farhan Hanif, Muhammad Kamran Siddiqui, and Fikre Bogale Petros
- Subjects
Topological indices ,Graph ,Chemical graph ,Curve fitting ,Gibbs energy (GE) ,Medicine ,Science - Abstract
Abstract Quantitative structure relationships linked to a chemical structure that shed light on its properties and chemical reactions are called topological indices. This structure is upset by the addition of silicon (Si) doping, which changes the electrical and optical characteristics. In this article, we examine the connection between a chemical structure’s Gibbs energy (GE) and K-Banhatti indices. In this article, we compute the K-Banhatti indices and then show the correlation between the indices and Gibb’s energy of the molecule using curve fitting. Through the curve fitting, we see that there is a strong correlation between indices and Gibb’s energy of a molecule. We use the polynomial curve fitting approach to see the correlation between indices and Gibb’s energy.
- Published
- 2024
- Full Text
- View/download PDF
33. Development model for assessing the structural complexity of programs
- Author
-
A.S. Rvanova, N.S. Kolyeva, and M.V. Panova
- Subjects
algorithm complexity ,metrics ,analysis ,estimation ,graph ,graph vertices ,modeling ,Home economics ,TX1-1110 ,Economics as a science ,HB71-74 - Abstract
The research is devoted to the estimation the structural complexity of programs. The algorithm of finding cyclomatic routes for program executions is described. By now, two directions of obtaining estimates for the complexity estimates in software modules have been defined: structural and statistical. Both directions connect the value of program complexity with the labor intensity related to their development. The structural complexity of program modules is determined by the number of interacting components, the number and complexity of links between them. The complexity of a program's behavior depends to a large extent on the set of routes through which it is executed. The complexity metric obtained from these positions allows us to determine estimates of the cost of designing the program as a whole, as well as to identify the modules that are likely to contain the most errors, especially the logical ones.
- Published
- 2024
- Full Text
- View/download PDF
34. The digital thread for system lifecycle management with a native graph database in a polyglot architecture.
- Author
-
Kasper, Nico, Pfenning, Michael, and Eigner, Martin
- Subjects
USER-centered system design ,VIRTUAL reality ,MACHINE learning ,ALGORITHMS ,WORK environment - Abstract
The Digital Thread is a system that connects different phases of the product lifecycle and the related data across one or more companies in the supply chain. This work aims to develop a graph data model of the Digital Thread, in the context of the vision of polyglot persistence, that interconnects the different phases of the lifecycle and their corresponding data models, processes, and IT systems. This work proposes a Digital Thread Graph that integrates a Digital Model and a derived Digital Twin, using object and relation attributes for view creation and filtering while minimizing redundancy. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
35. A novel approach towards utilizing graph analyzing objects arrangement – case studies from Airbnb homes in New York and Boston.
- Author
-
Yao, Yanhua
- Subjects
SPATIAL analysis (Statistics) ,URBAN homesteading ,HOME ownership ,EMPIRICAL research ,INTERIOR decoration - Abstract
The spatial arrangement of objects in residential environments is a crucial indicator of occupant behavior, shedding light on the complex dynamics of their interaction with the interior. This study introduces an object-based graph method for decoding urban home interiors, examining the co-presence of objects to uncover domestic behavioral patterns through indoor imagery analysis. By integrating centrality metrics with objects in graphs, we gain deeper insights into household behaviors, which provide empirical evidence for future interior design. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
36. Multimodal fused deep learning for drug property prediction: Integrating chemical language and molecular graph
- Author
-
Xiaohua Lu, Liangxu Xie, Lei Xu, Rongzhi Mao, Xiaojun Xu, and Shan Chang
- Subjects
Multimodal learning ,Deep learning ,Drug discovery ,Transformer ,Graph ,Biotechnology ,TP248.13-248.65 - Abstract
Accurately predicting molecular properties is a challenging but essential task in drug discovery. Recently, many mono-modal deep learning methods have been successfully applied to molecular property prediction. However, mono-modal learning is inherently limited as it relies solely on a single modality of molecular representation, which restricts a comprehensive understanding of drug molecules. To overcome the limitations, we propose a multimodal fused deep learning (MMFDL) model to leverage information from different molecular representations. Specifically, we construct a triple-modal learning model by employing Transformer-Encoder, Bidirectional Gated Recurrent Unit (BiGRU), and graph convolutional network (GCN) to process three modalities of information from chemical language and molecular graph: SMILES-encoded vectors, ECFP fingerprints, and molecular graphs, respectively. We evaluate the proposed triple-modal model using five fusion approaches on six molecule datasets, including Delaney, Llinas2020, Lipophilicity, SAMPL, BACE, and pKa from DataWarrior. The results show that the MMFDL model achieves the highest Pearson coefficients, and stable distribution of Pearson coefficients in the random splitting test, outperforming mono-modal models in accuracy and reliability. Furthermore, we validate the generalization ability of our model in the prediction of binding constants for protein-ligand complex molecules, and assess the resilience capability against noise. Through analysis of feature distributions in chemical space and the assigned contribution of each modal model, we demonstrate that the MMFDL model shows the ability to acquire complementary information by using proper models and suitable fusion approaches. By leveraging diverse sources of bioinformatics information, multimodal deep learning models hold the potential for successful drug discovery.
- Published
- 2024
- Full Text
- View/download PDF
37. Spanning [formula omitted]-trees and distance signless Laplacian spectral radius of graphs.
- Author
-
Zhou, Sizhong, Zhang, Yuli, and Liu, Hongxia
- Subjects
- *
GRAPH connectivity , *SPANNING trees , *EIGENVALUES , *LAPLACIAN matrices , *MOTIVATION (Psychology) - Abstract
A spanning k -tree of a connected graph G is a spanning tree in which each vertex admits degree at most k. It is easy to see that a spanning 2-tree is a Hamiltonian path. Hence, a spanning k -tree is an extended concept of a Hamiltonian path. Let Q (G) denote the distance signless Laplacian matrix of a graph G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. Liu and Li characterized a connected graph with a perfect matching with respect to the distance signless Laplacian spectral radius (Liu and Li, 2021). Win characterized a connected graph with a spanning k -tree via the number of connected components (Win, 1989). Motivated by Liu and Li's and Win's results, in this paper we investigate the relations between the spanning k -tree and the distance signless Laplacian spectral radius in a connected graph and prove an upper bound for η 1 (G) in a connected graph G to guarantee the existence of a spanning k -tree. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
38. A probabilistic algorithm for bounding the total restrained domination number of a [formula omitted] -free graph.
- Author
-
Joubert, Ernst J.
- Subjects
- *
DOMINATING set , *ALGORITHMS - Abstract
Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K 1 , ℓ -free graph with δ ≥ ℓ ≥ 3 and δ ≥ 5 , then γ t r (G) ≤ n 1 − (2 δ − 3) (2 δ) δ δ − 1 + o δ (1) . [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
39. The diagnosability of interconnection networks.
- Author
-
Wang, Mujiangshan, Xiang, Dong, Qu, Yi, and Li, Guohui
- Subjects
- *
GRAPH theory , *FAULT diagnosis , *COMPUTER science , *MATHEMATICS , *INTERSECTIONALITY - Abstract
Diagnosability is a fundamental consideration when designing an interconnected network. The PMC and MM ∗ fault diagnosis models are the two most commonly used models. Both the g -good-neighbour diagnosability and g -extra diagnosability of an interconnection network have been two of the hot topics in the intersectional research areas of Graph theory and Computer Science, which become increasingly attractive for new solutions to real-world problems. However, there are still some problems in the transformation from the concepts of Computer Science to that of mathematics. In this paper, we systematically study such problems and give a strict proof from concepts to mathematical conclusions. In the terms of results, we not only give the relationship between g -good-neighbour diagnosabilities of the network under PMC model and MM ∗ model, but also between g -extra diagnosabilities of the network under PMC and MM ∗ models. To apply our results, we give an application on the enhanced hypercube in the end and derive a lemma explaining whether these are 3-cycles in enhanced hypercubes and how many common neighbours for two vertices of enhanced hypercubes under different values of k in the meantime. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
40. Spanning k-trees and distance spectral radius in graphs.
- Author
-
Zhou, Sizhong and Wu, Jiancheng
- Subjects
- *
GRAPH connectivity , *INTEGERS , *TREES - Abstract
Let k ≥ 2 be an integer. A tree T is called a k-tree if d T (v) ≤ k for each v ∈ V (T) ; that is, the maximum degree of a k-tree is at most k. A k-tree T is a spanning k-tree if T is a spanning subgraph of a connected graph G. Let λ 1 (D (G)) denote the distance spectral radius in G, where D(G) denotes the distance matrix of G. In this paper, we verify an upper bound for λ 1 (D (G)) in a connected graph G to guarantee the existence of a spanning k-tree in G. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
41. Graph exploration by a deterministic memoryless automaton with pebbles.
- Author
-
Pattanayak, Debasish and Pelc, Andrzej
- Subjects
- *
PEBBLES , *ROBOTS , *MOBILE robots , *TREES - Abstract
A mobile agent, which is an autonomous device navigating in a graph, has to explore a given graph by visiting all of its nodes. We adopt the (arguably) weakest possible model of such a device: a deterministic memoryless automaton (DMA), i.e., a deterministic automaton with a single state. As expected, such a weak machine is incapable of exploring many graphs without marking nodes. Hence we allow the agent to use identical movable pebbles that can be dropped on nodes or picked from them. It turns out that this marking capability significantly enhances the exploration power of the agent. Our goal is to study how the availability of pebbles impacts the class of graphs that a DMA can explore. We first concentrate on finite graphs and show that any finite tree can be explored by a DMA without pebbles but there exist (small) finite graphs that cannot be explored by a DMA without pebbles. Then we turn attention to infinite graphs and fully characterize the class of infinite trees that can be explored by a DMA without pebbles. We also define a large class of infinite trees that can be explored by a DMA with finitely many pebbles. It turns out that many of these trees cannot be explored by a DMA without pebbles. On the other hand, we show a large class of infinite trees that cannot be explored by a DMA with finitely many pebbles. Thus, availability of pebbles yields a strict hierarchy of difficulty of exploration of infinite graphs by a DMA, and this hierarchy is strict even for the class of infinite trees: some trees can be explored without pebbles, some trees can be explored with finitely many pebbles but not without pebbles, and some trees require infinitely many pebbles. Finally, we consider exploration by a DMA with infinitely many pebbles. It turns out that all infinite trees can be explored by a DMA with infinitely many pebbles. By contrast, we construct infinite graphs that cannot be explored by any DMA, even with infinitely many pebbles. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
42. Disjoint isolating sets and graphs with maximum isolation number.
- Author
-
Boyer, Geoffrey and Goddard, Wayne
- Subjects
- *
GRAPH connectivity , *DOMINATING set - Abstract
An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
43. An inverse eigenvalue problem for structured matrices determined by graph pairs.
- Author
-
Berliner, A.H., Catral, M., Cavers, M., Kim, S., and van den Driessche, P.
- Subjects
- *
SYMMETRIC matrices , *INVERSE problems , *EIGENVALUES , *LOGICAL prediction , *MATRICES (Mathematics) - Abstract
Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
44. On non-bipartite graphs with strong reciprocal eigenvalue property.
- Author
-
Barik, Sasmita, Mishra, Rajiv, and Pati, Sukanta
- Subjects
- *
WEIGHTED graphs , *EIGENVALUES , *GRAPH connectivity , *MULTIPLICITY (Mathematics) , *BIPARTITE graphs , *TREES - Abstract
Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (property(R)) if A (G) is nonsingular, and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
45. The oriented chromatic number of the hexagonal grid is 6.
- Author
-
Lozano, Antoni
- Subjects
- *
HOMOMORPHISMS , *DIRECTED graphs - Abstract
The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χ o (F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H 2 , Bielak (2006) proved that 5 ≤ χ o (H 2) ≤ 6. Here we close the gap by showing that χ o (H 2) ≥ 6. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
46. Independence Number and Maximal Chromatic Polynomials of Connected Graphs.
- Author
-
Long, Shude and Cai, Junliang
- Abstract
Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k
holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
47. Vertex-primitive digraphs with large fixity.
- Author
-
Barbieri, Marco and Potočnik, Primož
- Abstract
The relative fixity of a digraph Γ is defined as the ratio between the largest number of vertices fixed by a nontrivial automorphism of Γ and the number of vertices of Γ . We characterize the vertex-primitive digraphs whose relative fixity is at least 1 3 , and we show that there are only finitely many vertex-primitive digraphs of bounded out-valency and relative fixity exceeding a positive constant. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
48. Creation of a Mathematical Model of a Stationary Rail Circuit in the Form of a Finite Discrete Automaton
- Author
-
V. V. Malovichko, N. V. Malovichko, and R. V. Rybalka
- Subjects
mathematical model ,discrete automaton ,diagnosis ,graph ,rail circuit ,microprocessor-based centralization ,Transportation engineering ,TA1001-1280 - Abstract
Purpose. Ensuring the safety of train traffic is a mandatory task in the development of technical equipment of railway transport in Ukraine. To diagnose and verify the performance of such systems, simulation models of overhead devices, in particular, the rail circle, are used. The most commonly used models are in the form of differential equations and in operator form. Unfortunately, they are not fully suitable for solving this problem. In this regard, there is a need to create a mathematical model that is easier to integrate for checking both relay electrical interlocking and microprocessor-based interlocking systems. Methodology. To achieve this goal, the authors proposed to create a mathematical model in the form of a finite discrete automaton. This paper considers the creation of a model of a station rail circuit as a directed graph. During the creation of the model, the input and output values of the model and the states are determined. The tables of inputs and outputs of the automaton are constructed, sequential expressions for the abstract model of the automaton are created, and their minimization is performed. The states of the automaton are coded using trigger circuits. Findings. In the course of the research, a mathematical model of the rail circle in the form of a Moore model finite automaton was created, and its performance was tested in the Proteus software environment. The developed model allows to simulate the operation of a stationary rail circuit at the level of abstraction, which operates with binary signals. This makes it possible to simplify the coordination of the model with microprocessor-based centralization software. In general, it is now possible to more effectively check the performance of microprocessor-based interlocking systems at the design and commissioning stages. Originality. The developed mathematical model makes it possible to determine the response of the microprocessor-based centralization software to the behavior of the rail circuit in various, in particular atypical, operating modes, as well as to determine the response of the station electrical centralization system to individual failures and to the occurrence of several failures simultaneously. Practical value. The proposed mathematical model can be used both to check the operation of microprocessor-based centralization systems at the design and implementation stages and for relay centralization systems when developing diagnostic complexes for monitoring their performance.
- Published
- 2024
- Full Text
- View/download PDF
49. Newly defined fuzzy Misbalance Prodeg Index with application in multi-criteria decision-making
- Author
-
Shama Liaqat, Zeeshan Saleem Mufti, and Yilun Shang
- Subjects
misbalance prodeg index ,graph ,fuzzy graph ,multi-criteria decision-making ,Mathematics ,QA1-939 - Abstract
In crisp graph theory, there are numerous topological indices accessible, including the Misbalance Prodeg Index, which is one of the most well-known degree-based topological indexes. In crisp graphs, both vertices and edges have membership values of $ 1 $ or $ 0 $, whereas in fuzzy graphs, both vertices and edges have different memberships. This is an entire contrast to the crisp graph. In this paper, we introduce the Fuzzy Misbalance Prodeg Index of a fuzzy graph, which is a generalized form of the Misbalance Prodeg Index of a graph. We find bounds of this index and find bounds of certain classes of graphs such as path graph, cycle graph, complete graph, complete bipartite graph, and star graph. We give an algorithm to find the Fuzzy Misbalance Prodeg Index of a graph for the model of multi-criteria decision-making is established. We present applications from daily life in multi-criteria decision-making. We apply our obtained model of the Fuzzy Misbalance Prodeg Index for the multi-criteria decision-making to the choice of the best supplier and we also show the graphical analysis of our index with the other indices that show how our index is better than other existing indices.
- Published
- 2024
- Full Text
- View/download PDF
50. Tight toughness bounds for path-factor critical avoidable graphs
- Author
-
Wenqi Wang and Guowei Dai
- Subjects
Graph ,path-factor ,toughness ,isolated toughness ,-factor critical avoidable graph ,05C38 ,Mathematics ,QA1-939 - Abstract
Given a graph G and an integer [Formula: see text], a spanning subgraph H of G is called a [Formula: see text]-factor of G if every component of H is a path with at least k vertices. A graph G is [Formula: see text]-factor avoidable if for every edge [Formula: see text], G has a [Formula: see text]-factor excluding e. A graph G is said to be [Formula: see text]-factor critical avoidable if the graph [Formula: see text] is [Formula: see text]-factor avoidable for any [Formula: see text] with [Formula: see text]. Here we study the sharp bounds of toughness and isolated toughness conditions for the existence of [Formula: see text]-factor critical avoidable graphs. In view of graph theory approaches, this paper mainly contributes to verify that (i) An [Formula: see text]-connected graph is [Formula: see text]-factor critical avoidable if its toughness [Formula: see text]; (ii) An [Formula: see text]-connected graph is [Formula: see text]-factor critical avoidable if its isolated toughness [Formula: see text].
- Published
- 2024
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.