Search results for: graphs
322 Domination Parameters of Middle Graphs: Connected and Outer-Connected Perspectives
Authors: Behnaz Pahlavsay, Farshad Kazemnejad, Elisa Palezzato, Michele Torielli
Abstract:
In this paper, we study the notions of connected domination number and of outer-connected domination number for middle graphs. Indeed, we obtain tight bounds for these numbers in terms of the order of the middle graph M(G). We also compute the outer-connected domination number of some families of graphs such as star graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and some operation on graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the outer-connected domination number of middle graphs.Keywords: connected domination number, outer-connected dom- ination number, domination number, middle graph, nordhaus- gaddum-like relation.
Procedia PDF Downloads 11321 Semirings of Graphs: An Approach Towards the Algebra of Graphs
Authors: Gete Umbrey, Saifur Rahman
Abstract:
Graphs are found to be most capable in computing, and its abstract structures have been applied in some specific computations and algorithms like in phase encoding controller, processor microcontroller, and synthesis of a CMOS switching network, etc. Being motivated by these works, we develop an independent approach to study semiring structures and various properties by defining the binary operations which in fact, seems analogous to an existing definition in some sense but with a different approach. This work emphasizes specifically on the construction of semigroup and semiring structures on the set of undirected graphs, and their properties are investigated therein. It is expected that the investigation done here may have some interesting applications in theoretical computer science, networking and decision making, and also on joining of two network systems.Keywords: graphs, join and union of graphs, semiring, weighted graphs
Procedia PDF Downloads 142320 Extremal Laplacian Energy of Threshold Graphs
Authors: Seyed Ahmad Mojallal
Abstract:
Let G be a connected threshold graph of order n with m edges and trace T. In this talk we give a lower bound on Laplacian energy in terms of n, m, and T of G. From this we determine the threshold graphs with the first four minimal Laplacian energies. We also list the first 20 minimal Laplacian energies among threshold graphs. Let σ=σ(G) be the number of Laplacian eigenvalues greater than or equal to average degree of graph G. Using this concept, we obtain the threshold graphs with the largest and the second largest Laplacian energies.Keywords: Laplacian eigenvalues, Laplacian energy, threshold graphs, extremal graphs
Procedia PDF Downloads 376319 An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem
Authors: Y. Wang
Abstract:
The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CNmaxn2) where C is the iterations, Nmax is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.Keywords: frequency quadrilateral, iterative algorithm, sparse graph, traveling salesman problem
Procedia PDF Downloads 226318 2D Structured Non-Cyclic Fuzzy Graphs
Authors: T. Pathinathan, M. Peter
Abstract:
Fuzzy graphs incorporate concepts from graph theory with fuzzy principles. In this paper, we make a study on the properties of fuzzy graphs which are non-cyclic and are of two-dimensional in structure. In particular, this paper presents 2D structure or the structure of double layer for a non-cyclic fuzzy graph whose underlying crisp graph is non-cyclic. In any graph structure, introducing 2D structure may lead to an inherent cycle. We propose relevant conditions for 2D structured non-cyclic fuzzy graphs. These conditions are extended even to fuzzy graphs of the 3D structure. General theoretical properties that are studied for any fuzzy graph are verified to 2D structured or double layered fuzzy graphs. Concepts like Order, Degree, Strong and Size for a fuzzy graph are studied for 2D structured or double layered non-cyclic fuzzy graphs. Using different types of fuzzy graphs, the proposed concepts relating to 2D structured fuzzy graphs are verified.Keywords: double layered fuzzy graph, double layered non–cyclic fuzzy graph, order, degree and size
Procedia PDF Downloads 391317 Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs
Authors: Swapnil Gupta, C. Pandu Rangan
Abstract:
A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.Keywords: uniquely restricted matching, interval graph, matching, induced matching, witness counting
Procedia PDF Downloads 383316 Building 1-Well-Covered Graphs by Corona, Join, and Rooted Product of Graphs
Authors: Vadim E. Levit, Eugen Mandrescu
Abstract:
A graph is well-covered if all its maximal independent sets are of the same size. A well-covered graph is 1-well-covered if deletion of every vertex of the graph leaves it well-covered. It is known that a graph without isolated vertices is 1-well-covered if and only if every two disjoint independent sets are included in two disjoint maximum independent sets. Well-covered graphs are related to combinatorial commutative algebra (e.g., every Cohen-Macaulay graph is well-covered, while each Gorenstein graph without isolated vertices is 1-well-covered). Our intent is to construct several infinite families of 1-well-covered graphs using the following known graph operations: corona, join, and rooted product of graphs. Adopting some known techniques used to advantage for well-covered graphs, one can prove that: if the graph G has no isolated vertices, then the corona of G and H is 1-well-covered if and only if H is a complete graph of order two at least; the join of the graphs G and H is 1-well-covered if and only if G and H have the same independence number and both are 1-well-covered; if H satisfies the property that every three pairwise disjoint independent sets are included in three pairwise disjoint maximum independent sets, then the rooted product of G and H is 1-well-covered, for every graph G. These findings show not only how to generate some more families of 1-well-covered graphs, but also that, to this aim, sometimes, one may use graphs that are not necessarily 1-well-covered.Keywords: maximum independent set, corona, concatenation, join, well-covered graph
Procedia PDF Downloads 198315 Reductions of Control Flow Graphs
Authors: Robert Gold
Abstract:
Control flow graphs are a well-known representation of the sequential control flow structure of programs with a multitude of applications. Not only single functions but also sets of functions or complete programs can be modelled by control flow graphs. In this case the size of the graphs can grow considerably and thus makes it difficult for software engineers to analyse the control flow. Graph reductions are helpful in this situation. In this paper we define reductions to subsets of nodes. Since executions of programs are represented by paths through the control flow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.Keywords: control flow graph, graph reduction, software engineering, software applications
Procedia PDF Downloads 544314 Nullity of t-Tupple Graphs
Authors: Khidir R. Sharaf, Didar A. Ali
Abstract:
The nullity η (G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f (w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced sub-graph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the end vertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs. Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.Keywords: graph theory, graph spectra, nullity of graphs, statistic
Procedia PDF Downloads 235313 On the Zeros of the Degree Polynomial of a Graph
Authors: S. R. Nayaka, Putta Swamy
Abstract:
Graph polynomial is one of the algebraic representations of the Graph. The degree polynomial is one of the simple algebraic representations of graphs. The degree polynomial of a graph G of order n is the polynomial Deg(G, x) with the coefficients deg(G,i) where deg(G,i) denotes the number of vertices of degree i in G. In this article, we investigate the behavior of the roots of some families of Graphs in the complex field. We investigate for the graphs having only integral roots. Further, we characterize the graphs having single roots or having real roots and behavior of the polynomial at the particular value is also obtained.Keywords: degree polynomial, regular graph, minimum and maximum degree, graph operations
Procedia PDF Downloads 237312 Jordan Curves in the Digital Plane with Respect to the Connectednesses given by Certain Adjacency Graphs
Authors: Josef Slapal
Abstract:
Digital images are approximations of real ones and, therefore, to be able to study them, we need the digital plane Z2 to be equipped with a convenient structure that behaves analogously to the Euclidean topology on the real plane. In particular, it is required that such a structure allows for a digital analogue of the Jordan curve theorem. We introduce certain adjacency graphs on the digital plane and prove digital Jordan curves for them thus showing that the graphs provide convenient structures on Z2 for the study and processing of digital images. Further convenient structures including the wellknown Khalimsky and Marcus-Wyse adjacency graphs may be obtained as quotients of the graphs introduced. Since digital Jordan curves represent borders of objects in digital images, the adjacency graphs discussed may be used as background structures on the digital plane for solving the problems of digital image processing that are closely related to borders like border detection, contour filling, pattern recognition, thinning, etc.Keywords: digital plane, adjacency graph, Jordan curve, quotient adjacency
Procedia PDF Downloads 373311 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements
Authors: Shin-Shin Kao, Yuan-Kang Shih, Hsun Su
Abstract:
In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.Keywords: complement, degree sum, hamiltonian, tough
Procedia PDF Downloads 284310 Improvement a Lower Bound of Energy for Some Family of Graphs, Related to Determinant of Adjacency Matrix
Authors: Saieed Akbari, Yousef Bagheri, Amir Hossein Ghodrati, Sima Saadat Akhtar
Abstract:
Let G be a simple graph with the vertex set V (G) and with the adjacency matrix A (G). The energy E (G) of G is defined to be the sum of the absolute values of all eigenvalues of A (G). Also let n and m be number of edges and vertices of the graph respectively. A regular graph is a graph where each vertex has the same number of neighbours. Given a graph G, its line graph L(G) is a graph such that each vertex of L(G) represents an edge of G; and two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint in G. In this paper we show that for every regular graphs and also for every line graphs such that (G) 3 we have, E(G) 2nm + n 1. Also at the other part of the paper we prove that 2 (G) E(G) for an arbitrary graph G.Keywords: eigenvalues, energy, line graphs, matching number
Procedia PDF Downloads 223309 Upper Bounds on the Paired Domination Number of Cubic Graphs
Authors: Bin Sheng, Changhong Lu
Abstract:
Let G be a simple undirected graph with no isolated vertex. A paired dominating set of G is a dominating set which induces a subgraph that has a perfect matching. The paired domination number of G, denoted by γₚᵣ(G), is the size of its smallest paired dominating set. Goddard and Henning conjectured that γₚᵣ(G) ≤ 4n/7 holds for every graph G with δ(G) ≥ 3, except the Petersen Graph. In this paper, we prove this conjecture for cubic graphs.Keywords: paired dominating set, upper bound, cubic graphs, weight function
Procedia PDF Downloads 235308 Graph Similarity: Algebraic Model and Its Application to Nonuniform Signal Processing
Authors: Nileshkumar Vishnav, Aditya Tatu
Abstract:
A recent approach of representing graph signals and graph filters as polynomials is useful for graph signal processing. In this approach, the adjacency matrix plays pivotal role; instead of the more common approach involving graph-Laplacian. In this work, we follow the adjacency matrix based approach and corresponding algebraic signal model. We further expand the theory and introduce the concept of similarity of two graphs. The similarity of graphs is useful in that key properties (such as filter-response, algebra related to graph) get transferred from one graph to another. We demonstrate potential applications of the relation between two similar graphs, such as nonuniform filter design, DTMF detection and signal reconstruction.Keywords: graph signal processing, algebraic signal processing, graph similarity, isospectral graphs, nonuniform signal processing
Procedia PDF Downloads 339307 Hosoya Polynomials of Zero-Divisor Graphs
Authors: Abdul Jalil M. Khalaf, Esraa M. Kadhim
Abstract:
The Hosoya polynomial of a graph G is a graphical invariant polynomial that its first derivative at x= 1 is equal to the Wiener index and second derivative at x=1 is equal to the Hyper-Wiener index. In this paper we study the Hosoya polynomial of zero-divisor graphs.Keywords: Hosoya polynomial, wiener index, Hyper-Wiener index, zero-divisor graphs
Procedia PDF Downloads 522306 The K-Distance Neighborhood Polynomial of a Graph
Authors: Soner Nandappa D., Ahmed Mohammed Naji
Abstract:
In a graph G = (V, E), the distance from a vertex v to a vertex u is the length of shortest v to u path. The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity. The k-distance neighborhood of v, for 0 ≤ k ≤ e(v), is Nk(v) = {u ϵ V (G) : d(v, u) = k}. In this paper, we introduce a new distance degree based topological polynomial of a graph G is called a k- distance neighborhood polynomial, denoted Nk(G, x). It is a polynomial with the coefficient of the term k, for 0 ≤ k ≤ e(v), is the sum of the cardinalities of Nk(v) for every v ϵ V (G). Some properties of k- distance neighborhood polynomials are obtained. Exact formulas of the k- distance neighborhood polynomial for some well-known graphs, Cartesian product and join of graphs are presented.Keywords: vertex degrees, distance in graphs, graph operation, Nk-polynomials
Procedia PDF Downloads 536305 Surface to the Deeper: A Universal Entity Alignment Approach Focusing on Surface Information
Authors: Zheng Baichuan, Li Shenghui, Li Bingqian, Zhang Ning, Chen Kai
Abstract:
Entity alignment (EA) tasks in knowledge graphs often play a pivotal role in the integration of knowledge graphs, where structural differences often exist between the source and target graphs, such as the presence or absence of attribute information and the types of attribute information (text, timestamps, images, etc.). However, most current research efforts are focused on improving alignment accuracy, often along with an increased reliance on specific structures -a dependency that inevitably diminishes their practical value and causes difficulties when facing knowledge graph alignment tasks with varying structures. Therefore, we propose a universal knowledge graph alignment approach that only utilizes the common basic structures shared by knowledge graphs. We have demonstrated through experiments that our method achieves state-of-the-art performance in fair comparisons.Keywords: knowledge graph, entity alignment, transformer, deep learning
Procedia PDF Downloads 36304 The Analysis of Split Graphs in Social Networks Based on the k-Cardinality Assignment Problem
Authors: Ivan Belik
Abstract:
In terms of social networks split graphs correspond to the variety of interpersonal and intergroup relations. In this paper we analyse the interaction between the cliques (socially strong and trusty groups) and the independent sets (fragmented and non-connected groups of people) as the basic components of any split graph. Based on the Semi-Lagrangean relaxation for the k-cardinality assignment problem we show the way of how to minimize the socially risky interactions between the cliques and the independent sets within the social network.Keywords: cliques, independent sets, k-cardinality assignment, social networks, split graphs
Procedia PDF Downloads 312303 Hosoya Polynomials of Mycielskian Graphs
Authors: Sanju Vaidya, Aihua Li
Abstract:
Vulnerability measures and topological indices are crucial in solving various problems such as the stability of the communication networks and development of mathematical models for chemical compounds. In 1947, Harry Wiener introduced a topological index related to molecular branching. Now there are more than 100 topological indices for graphs. For example, Hosoya polynomials (also called Wiener polynomials) were introduced to derive formulas for certain vulnerability measures and topological indices for various graphs. In this paper, we will find a relation between the Hosoya polynomials of any graph and its Mycielskian graph. Additionally, using this we will compute vulnerability measures, closeness and betweenness centrality, and extended Wiener indices. It is fascinating to see how Hosoya polynomials are useful in the two diverse fields, cybersecurity and chemistry.Keywords: hosoya polynomial, mycielskian graph, graph vulnerability measure, topological index
Procedia PDF Downloads 62302 Location-Domination on Join of Two Graphs and Their Complements
Authors: Analen Malnegro, Gina Malacas
Abstract:
Dominating sets and related topics have been studied extensively in the past few decades. A dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. Some problems involving detection devices can be modeled with graphs. Finding the minimum number of devices needed according to the type of devices and the necessity of locating the object gives rise to locating-dominating sets. A subset S of vertices of a graph G is called locating-dominating set, LD-set for short, if it is a dominating set and if every vertex v not in S is uniquely determined by the set of neighbors of v belonging to S. The location-domination number λ(G) is the minimum cardinality of an LD-set for G. The complement of a graph G is a graph Ḡ on same vertices such that two distinct vertices of Ḡ are adjacent if and only if they are not adjacent in G. An LD-set of a graph G is global if it is an LD-set of both G and its complement Ḡ. The global location-domination number λg(G) is defined as the minimum cardinality of a global LD-set of G. In this paper, global LD-sets on the join of two graphs are characterized. Global location-domination numbers of these graphs are also determined.Keywords: dominating set, global locating-dominating set, global location-domination number, locating-dominating set, location-domination number
Procedia PDF Downloads 180301 Improoving Readability for Tweet Contextualization Using Bipartite Graphs
Authors: Amira Dhokar, Lobna Hlaoua, Lotfi Ben Romdhane
Abstract:
Tweet contextualization (TC) is a new issue that aims to answer questions of the form 'What is this tweet about?' The idea of this task was imagined as an extension of a previous area called multi-document summarization (MDS), which consists in generating a summary from many sources. In both TC and MDS, the summary should ideally contain the most relevant information of the topic that is being discussed in the source texts (for MDS) and related to the query (for TC). Furthermore of being informative, a summary should be coherent, i.e. well written to be readable and grammatically compact. Hence, coherence is an essential characteristic in order to produce comprehensible texts. In this paper, we propose a new approach to improve readability and coherence for tweet contextualization based on bipartite graphs. The main idea of our proposed method is to reorder sentences in a given paragraph by combining most expressive words detection and HITS (Hyperlink-Induced Topic Search) algorithm to make up a coherent context.Keywords: bipartite graphs, readability, summarization, tweet contextualization
Procedia PDF Downloads 184300 Graph Codes - 2D Projections of Multimedia Feature Graphs for Fast and Effective Retrieval
Authors: Stefan Wagenpfeil, Felix Engel, Paul McKevitt, Matthias Hemmje
Abstract:
Multimedia Indexing and Retrieval is generally designed and implemented by employing feature graphs. These graphs typically contain a significant number of nodes and edges to reflect the level of detail in feature detection. A higher level of detail increases the effectiveness of the results but also leads to more complex graph structures. However, graph-traversal-based algorithms for similarity are quite inefficient and computation intensive, especially for large data structures. To deliver fast and effective retrieval, an efficient similarity algorithm, particularly for large graphs, is mandatory. Hence, in this paper, we define a graph-projection into a 2D space (Graph Code) as well as the corresponding algorithms for indexing and retrieval. We show that calculations in this space can be performed more efficiently than graph-traversals due to a simpler processing model and a high level of parallelization. In consequence, we prove that the effectiveness of retrieval also increases substantially, as Graph Codes facilitate more levels of detail in feature fusion. Thus, Graph Codes provide a significant increase in efficiency and effectiveness (especially for Multimedia indexing and retrieval) and can be applied to images, videos, audio, and text information.Keywords: indexing, retrieval, multimedia, graph algorithm, graph code
Procedia PDF Downloads 150299 Multiple Version of Roman Domination in Graphs
Authors: J. C. Valenzuela-Tripodoro, P. Álvarez-Ruíz, M. A. Mateos-Camacho, M. Cera
Abstract:
In 2004, it was introduced the concept of Roman domination in graphs. This concept was initially inspired and related to the defensive strategy of the Roman Empire. An undefended place is a city so that no legions are established on it, whereas a strong place is a city in which two legions are deployed. This situation may be modeled by labeling the vertices of a finite simple graph with labels {0, 1, 2}, satisfying the condition that any 0-vertex must be adjacent to, at least, a 2-vertex. Roman domination in graphs is a variant of classic domination. Clearly, the main aim is to obtain such labeling of the vertices of the graph with minimum cost, that is to say, having minimum weight (sum of all vertex labels). Formally, a function f: V (G) → {0, 1, 2} is a Roman dominating function (RDF) in the graph G = (V, E) if f(u) = 0 implies that f(v) = 2 for, at least, a vertex v which is adjacent to u. The weight of an RDF is the positive integer w(f)= ∑_(v∈V)▒〖f(v)〗. The Roman domination number, γ_R (G), is the minimum weight among all the Roman dominating functions? Obviously, the set of vertices with a positive label under an RDF f is a dominating set in the graph, and hence γ(G)≤γ_R (G). In this work, we start the study of a generalization of RDF in which we consider that any undefended place should be defended from a sudden attack by, at least, k legions. These legions can be deployed in the city or in any of its neighbours. A function f: V → {0, 1, . . . , k + 1} such that f(N[u]) ≥ k + |AN(u)| for all vertex u with f(u) < k, where AN(u) represents the set of active neighbours (i.e., with a positive label) of vertex u, is called a [k]-multiple Roman dominating functions and it is denoted by [k]-MRDF. The minimum weight of a [k]-MRDF in the graph G is the [k]-multiple Roman domination number ([k]-MRDN) of G, denoted by γ_[kR] (G). First, we prove that the [k]-multiple Roman domination decision problem is NP-complete even when restricted to bipartite and chordal graphs. A problem that had been resolved for other variants and wanted to be generalized. We know the difficulty of calculating the exact value of the [k]-MRD number, even for families of particular graphs. Here, we present several upper and lower bounds for the [k]-MRD number that permits us to estimate it with as much precision as possible. Finally, some graphs with the exact value of this parameter are characterized.Keywords: multiple roman domination function, decision problem np-complete, bounds, exact values
Procedia PDF Downloads 102298 Selection of Designs in Ordinal Regression Models under Linear Predictor Misspecification
Authors: Ishapathik Das
Abstract:
The purpose of this article is to find a method of comparing designs for ordinal regression models using quantile dispersion graphs in the presence of linear predictor misspecification. The true relationship between response variable and the corresponding control variables are usually unknown. Experimenter assumes certain form of the linear predictor of the ordinal regression models. The assumed form of the linear predictor may not be correct always. Thus, the maximum likelihood estimates (MLE) of the unknown parameters of the model may be biased due to misspecification of the linear predictor. In this article, the uncertainty in the linear predictor is represented by an unknown function. An algorithm is provided to estimate the unknown function at the design points where observations are available. The unknown function is estimated at all points in the design region using multivariate parametric kriging. The comparison of the designs are based on a scalar valued function of the mean squared error of prediction (MSEP) matrix, which incorporates both variance and bias of the prediction caused by the misspecification in the linear predictor. The designs are compared using quantile dispersion graphs approach. The graphs also visually depict the robustness of the designs on the changes in the parameter values. Numerical examples are presented to illustrate the proposed methodology.Keywords: model misspecification, multivariate kriging, multivariate logistic link, ordinal response models, quantile dispersion graphs
Procedia PDF Downloads 385297 First-Year Undergraduate Students' Dilemma with Kinematics Graphs
Authors: Itumeleng Phage
Abstract:
Students’ comprehension of graphs may be affected by the characteristics of the discipline in which the graph is used, the type of the task as well as the background of the students who are the readers or interpreters of the graph. This research study investigated these aspects of the graph comprehension of 152 first-year undergraduate physics students by comparing their responses to corresponding tasks in the mathematics and physics disciplines. The discipline characteristics were analysed for four task-related constructs namely coordinates, representations, area and slope. Students’ responses to corresponding visual decoding and judgement tasks set in mathematics and kinematics contexts were statistically compared. The effects of the participants’ gender, year of school completion and study course were determined as reader characteristics. The results of the empirical study indicated that participants generally transferred their mathematics knowledge on coordinates and representation of straight line graphs to the physics contexts, but not in the cases of parabolic and hyperbolic functions or area under graphs. Insufficient understanding of the slope concept contributed to weak performances on this construct in both mathematics and physics contexts. Discipline characteristics seem to play a vital role in students’ understanding, while reader characteristics had insignificant to medium effects on their responses.Keywords: kinematics graph, discipline characteristics, constructs, coordinates, representations, area and slope
Procedia PDF Downloads 253296 A Forbidden-Minor Characterization for the Class of Co-Graphic Matroids Which Yield the Graphic Element-Splitting Matroids
Authors: Prashant Malavadkar, Santosh Dhotre, Maruti Shikare
Abstract:
The n-point splitting operation on graphs is used to characterize 4-connected graphs with some more operations. Element splitting operation on binary matroids is a natural generalization of the notion of n-point splitting operation on graphs. The element splitting operation on a graphic (cographic) matroid may not yield a graphic (cographic) matroid. Characterization of graphic (cographic) matroids whose element splitting matroids are graphic (cographic) is known. The element splitting operation on a co-graphic matroid, in general may not yield a graphic matroid. In this paper, we give a necessary and sufficient condition for the cographic matroid to yield a graphic matroid under the element splitting operation. In fact, we prove that the element splitting operation, by any pair of elements, on a cographic matroid yields a graphic matroid if and only if it has no minor isomorphic to M(K4); where K4 is the complete graph on 4 vertices.Keywords: binary matroids, splitting, element splitting, forbidden minor
Procedia PDF Downloads 270295 Problem Solving in Chilean Higher Education: Figurations Prior in Interpretations of Cartesian Graphs
Authors: Verónica Díaz
Abstract:
A Cartesian graph, as a mathematical object, becomes a tool for configuration of change. Its best comprehension is done through everyday life problem-solving associated with its representation. Despite this, the current educational framework favors general graphs, without consideration of their argumentation. Students are required to find the mathematical function without associating it to the development of graphical language. This research describes the use made by students of configurations made prior to Cartesian graphs with regards to an everyday life problem related to a time and distance variation phenomenon. The theoretical framework describes the function conditions of study and their modeling. This is a qualitative, descriptive study involving six undergraduate case studies that were carried out during the first term in 2016 at University of Los Lagos. The research problem concerned the graphic modeling of a real person’s movement phenomenon, and two levels of analysis were identified. The first level aims to identify local and global graph interpretations; a second level describes the iconicity and referentiality degree of an image. According to the results, students were able to draw no figures before the Cartesian graph, highlighting the need for students to represent the context and the movement of which causes the phenomenon change. From this, they managed Cartesian graphs representing changes in position, therefore, achieved an overall view of the graph. However, the local view only indicates specific events in the problem situation, using graphic and verbal expressions to represent movement. This view does not enable us to identify what happens on the graph when the movement characteristics change based on possible paths in the person’s walking speed.Keywords: cartesian graphs, higher education, movement modeling, problem solving
Procedia PDF Downloads 215294 A New Bound on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based on Bipartite Graphs of Larger Girth
Authors: Hui-Chuan Lu
Abstract:
In a perfect secret-sharing scheme, a dealer distributes a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of the participants in any unqualified subset is statistically independent of the secret. The access structure of the scheme refers to the collection of all qualified subsets. In a graph-based access structures, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. We study the optimal average information ratio of the access structures based on bipartite graphs. Based on some previous results, we give a bound on the optimal average information ratio for all bipartite graphs of girth at least six. This bound is the best possible for some classes of bipartite graphs using our approach.Keywords: secret-sharing scheme, average information ratio, star covering, deduction, core cluster
Procedia PDF Downloads 355293 Some Conjectures and Programs about Computing the Detour Index of Molecular Graphs of Nanotubes
Authors: Shokofeh Ebrtahimi
Abstract:
Let G be the chemical graph of a molecule. The matrix D = [dij ] is called the detour matrix of G, if dij is the length of longest path between atoms i and j. The sum of all entries above the main diagonal of D is called the detour index of G.Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena.[1] The pioneers of the chemical graph theory are Alexandru Balaban, Ante Graovac, Ivan Gutman, Haruo Hosoya, Milan Randić and Nenad TrinajstićLet G be the chemical graph of a molecule. The matrix D = [dij ] is called the detour matrix of G, if dij is the length of longest path between atoms i and j. The sum of all entries above the main diagonal of D is called the detour index of G. In this paper, a new program for computing the detour index of molecular graphs of nanotubes by heptagons is determineded. Some Conjectures about detour index of Molecular graphs of nanotubes is included.Keywords: chemical graph, detour matrix, Detour index, carbon nanotube
Procedia PDF Downloads 284