Search

In this study, we employ the Sachs graph theory to formulate the conduction properties of a single-molecular junction consisting of a molecule in which one carbon atom of an alternant hydrocarbon is replaced with a heteroatom. The derived formula includes odd and even powers of the adjacency matrix, unlike the graph of the parental structure. These powers correspond to odd- and even-length walks. Furthermore, because the heteroatom is represented as a self-loop of unit length in the graph, an odd number of passes of the self-loop will change the parity of the length of the walk. To confirm the aforementioned effects of heteroatoms on conduction in an actual sample, the conduction behavior of meta-connected molecular junctions consisting of a heterocyclic six-membered ring, whose conductive properties have already been experimentally determined, was analyzed based on the enumerated number of walks. [ABSTRACT FROM AUTHOR]

A facial-parity edge-coloring of a 2-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. A facial-parity vertex-coloring of a 2-connected plane graph is a proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Czap and Jendroľ in [Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703], conjectured that 10 colors suffice in both colorings. We present an infinite family of counterexamples to both conjectures. A facial (Pk, Pl)-WORM coloring of a plane graph G is a vertex-coloring such that G contains neither rainbow facial k-path nor monochromatic facial l-path. Czap, Jendroľ and Valiska in [WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368], proved that for any integer n ≥ 12 there exists a connected plane graph on n vertices, with maximum degree at least 6, having no facial (P3, P3)-WORM coloring. They also asked whether there exists a graph with maximum degree 4 having the same property. We prove that for any integer n ≥ 18, there exists a connected plane graph, with maximum degree 4, with no facial (P3, P3)-WORM coloring. [ABSTRACT FROM AUTHOR]

In Ramsey Theory for graphs we are given a graph G and we are required to find the least n0 such that, for any n ≥ n0, any red/blue colouring of the edges of Kn gives a subgraph G all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of Kn, there must be a copy of G such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when G has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of G which, if it exists, is the minimum integer bal(n, G) such that, for any red/blue colouring of E(Kn) with more than bal(n, G) edges of either colour, Kn will contain a balanced coloured copy of G as described above. The strong balance number sbal(n,G) is analogously defined when G has an odd number of edges, but in this case we require that there are copies of G with both one more red edge and one more blue edge. These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(n, G) which requires copies of G containing a complete distribution of the number of red and blue edges over E(G). In this paper we shall catalogue bal(n, G), sbal(n, G) and ot(n, G) for all graphs G on at most four edges. We shall be using some of the key results of Caro et al. which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable. [ABSTRACT FROM AUTHOR]

Timber is a two player game played on a directed graph, with a domino on each arc. The direction of an arc indicates the direction its domino can be toppled. Once a domino is toppled, it creates a chain reaction toppling all dominoes along that direction, and the player who topples the last domino wins. A P -position is an orientation of the edges of the graph where the second player can always force a win. A connected graph with a cycle has no P -position, thus Timber is a game studied in trees. We prove that a tree has a P -position if and only if the number of edges is even, which generalizes the existing characterization for paths and improves the performance of the existing algorithm to decide if an oriented tree with an odd number of arcs is a P -position. We contribute to the open problem of determining the number of P -positions of a tree. We compute the number of P -positions of three caterpillar infinite subclasses. Finally, we present a lower bound to the number of P -positions of an arbitrary caterpillar. [ABSTRACT FROM AUTHOR]

In this article, we study the structure of the graph implied by a given map on the set Sp = {1, 2, . . ., p - 1}, where p is an odd prime. The consecutive applications of the map generate an integer sequence, or in graph theoretical context a walk, that is linked to the discrete logarithm problem. [ABSTRACT FROM AUTHOR]

We study the class of simple graphs G ∗ for which every pair of distinct odd cycles intersect in at most one edge. We give a structural characterization of the graphs in G ∗ and prove that every G ∈ G ∗ satisfies the list-edge-coloring conjecture. When Δ ( G ) ≥ 4 , we in fact prove a stronger result about kernel-perfect orientations in L ( G ) which implies that G is ( m Δ ( G ) : m ) -edge-choosable and Δ ( G ) -edge-paintable for every m ≥ 1 . [ABSTRACT FROM AUTHOR]

Let n ≥ 1 be an odd integer. For every 1 ≤ i ≤ n let si = (ai, bi ) be an open unit segment on the real line. Let 0 ≤ ϵ < 1/2 be fixed. Color by green all the points (numbers) on the real line of the form ai + ϵ and bi - ϵ. Then there exists at least one green point that belongs to an odd number of the segments s1, . . . , sn. [ABSTRACT FROM AUTHOR]

The matching preclusion number of a graph is the minimum number of edges whose deletion results the remaining graph that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that the matching preclusion number of k -ary n -cubes is 4 n − 1 except k = 3 and n = 2 , where k is odd and k ≥ 3 . [ABSTRACT FROM AUTHOR]

Generalized Fibonacci cube Q ( f), introduced by Ilić, Klavžar and Rho, is the graph obtained from the hypercube Q by removing all vertices that contain f as factor. A word f is good if Q ( f) is an isometric subgraph of Q for all d ≥ 1, and bad otherwise. A non-extendable sequence of contiguous equal digits in a word μ is called a block of μ. Ilić, Klavžar and Rho shown that all the words consisting of one block are good, and all the words consisting of three blocks are bad. So a natural problem is to study the words consisting of other odd number of blocks. In the present paper, a necessary condition for a word consisting of odd number of blocks being good is given, and all the good (bad) words consisting of 5 blocks is determined. [ABSTRACT FROM AUTHOR]

The article focuses on the Math Madness project for proliferation of mathematics education among elementary school students through deployment of graph theory with graph coloring approaches. Topics discussed include assessment of mathematical problems related to polygons for students through graph theory; reinforcement of provisions related to the Common Core State Standards for Mathematics (CCSSM); and enhancement of mathematical discourse among students regarding odd and even numbers.

In this paper, we introduce a new labeling called odd vertex equitable even labeling. Let G be a graph with p vertices and q edges and A = {1, 3, . . ., q} if q is odd or A = {1, 3, . . ., q + 1} if q is even. A graph G is said to admit an odd vertex equitable even labeling if there exists a vertex labeling f : V (G) → A that induces an edge labeling f∗ defined by f ∗(uv) = f (u)+f (v) for all edges uv such that for all a and b in A, |vf(a) - vf(b)| ≤ 1 and the induced edge labels are 2, 4, . . ., 2q where vf(a) be the number of vertices v with f(v) = a for a ∈ A. A graph that admits odd vertex equitable even labeling is called odd vertex equitable even graph. We investigate the odd vertex equitable even behavior of some standard graphs. [ABSTRACT FROM AUTHOR]

A labeling or numbering of a graph G is an assignment f of labels to the vertices of G that induces for each edge uv a labeling depending on the vertex labels f(u) and f(v). In this paper we study some new families of odd graceful graphs. [ABSTRACT FROM AUTHOR]

Continuing our earlier work on partitions with non-repeating odd parts and q-hypergeometric identities, we now study these partitions combinatorially by representing them in terms of 2-modular Ferrers graphs. This yields certain weighted partition identities with free parameters. By special choices of these parameters, we connect them to the Göllnitz-Gordon partitions, and combinatorially prove a modular identity and some parity results. As a consequence, we derive a shifted partition theorem mod 32 of Andrews. Finally we discuss basis partitions in connection with the 2-modular representation of partitions with non-repeating odd parts, and deduce two new parity results involving partial theta series. [ABSTRACT FROM AUTHOR]

A triple of vertices in a graph is a frustrated triangle if it induces an odd number of edges. We study the set F n ⊂ [ 0 , ( n 3 ) ] of possible number of frustrated triangles f ( G ) in a graph G on n vertices. We prove that about two thirds of the numbers in [ 0 , n 3 / 2 ] cannot appear in F n , and we characterise the graphs G with f ( G ) ∈ [ 0 , n 3 / 2 ] . More precisely, our main result is that, for each n ≥ 3 , F n contains two interlacing sequences 0 = a 0 ≤ b 0 ≤ a 1 ≤ b 1 ≤ ⋯ ≤ a m ≤ b m ∼ n 3 / 2 such that F n ∩ ( b t , a t + 1 ) = 0̸ for all t , where the gaps are | b t − a t + 1 | = ( n − 2 ) − t ( t + 1 ) and | a t − b t | = t ( t − 1 ) . Moreover, f ( G ) ∈ [ a t , b t ] if and only if G can be obtained from a complete bipartite graph by flipping exactly t edges/nonedges. On the other hand, we show, for all n sufficiently large, that if m ∈ [ f ( n ) , ( n 3 ) − f ( n ) ] , then m ∈ F n where f ( n ) is asymptotically best possible with f ( n ) ∼ n 3 / 2 for n even and f ( n ) ∼ 2 n 3 / 2 for n odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with n vertices and e ≤ n 2 / 4 edges. [ABSTRACT FROM AUTHOR]

Suppose in a graph G vertices can be either red or blue. Let k be odd. At each time step, each vertex v in G polls k random neighbours and takes the majority colour. If it does not have k neighbours, it simply polls all of them, or all less one if the degree of v is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of G is red independently with probability α < 1 2 , and is otherwise blue. We show that if α is sufficiently biased, then with high probability consensus is reached on the initial global majority within O ( log k log k n ) steps if 5 ≤ k ≤ d , and O ( log d log d n ) steps if k > d . Here, d ≥ 5 is the effective minimum degree, the smallest integer which occurs Θ ( n ) times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least Ω ( log d log d n ) , with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the Erdős–Rényi random graphs in the connected regime. [ABSTRACT FROM AUTHOR]

Abstract: A broadcast graph is a connected graph, , , in which each vertex can complete broadcasting of one message within at most time units. A minimum broadcast graph on vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on vertices. The cardinality of the edge set of such a graph is denoted by . In this paper we construct a new broadcast graph with , for and , for , where , for even and for odd , , and if and if . The new bound is an improvement upon the bounds appeared in Bermond et al. (1995), Bermond et al. (1997), Fertin and Raspaud (2004) and Harutyunyan and Leistman (1999) and the recent bound presented by Harutyunyan and Liestman (2012) for odd values of . [Copyright &y& Elsevier]

Abstract: A characterization is given of the class of edge-transitive Cayley graphs of Frobenius groups with r an odd prime and m odd, of valency less than with the smallest prime divisor of m. It is shown that either , or such a graph is a normal Cayley graph and half-transitive. This provides new construction of half-transitive graphs. [Copyright &y& Elsevier]

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the coloring we construct is proper. This proves a conjecture of Czap and Jendrol' [Discuss. Math. Graph Theory 29 (2009), pp. 521-543.]. We also provide examples showing that eight colors may be necessary (ten when restricted to proper colorings). [ABSTRACT FROM AUTHOR]

Abstract: A facial parity edge coloring of a 2-edge connected plane graph is an edge coloring where no two consecutive edges of a facial trail of any face receive the same color. Additionally, for every face and every color either no edge or an odd number of edges incident to is colored by . Czap, Jendrol’, Kardoš and Soták (2012) [6] showed that every 2-edge connected plane graph admits a facial parity edge coloring with at most 20 colors. We improve this bound to 16. [Copyright &y& Elsevier]

Let G be a simple graph. The domination polynomial of a graph G of order n is the polynomial $${D(G,x)=\sum_{i=0}^{n} d(G,i) x^{i}}$$ , where d( G, i) is the number of dominating sets of G of size i. In this article we investigate the domination polynomial at −1. We give a construction showing that for each odd number n there is a connected graph G with D( G, −1) = n. [ABSTRACT FROM AUTHOR]

Abstract: The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutteʼs 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is -connected, Jaegerʼs circular flow conjecture (1984) that for every odd natural number , every -edge-connected graph has a modulo k-orientation, etc. It was proved recently by Thomassen that, for every odd number , every -edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G is -connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassenʼs method is refined to prove the following: For every odd number , every -edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is -connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs. [Copyright &y& Elsevier]

An elementary approach for finding non-trivial parametric solutions to homogeneous symmetric Diophantine equations of odd degree in sufficiently many variables is presented. The method is based on studying a model case of quintic symmetric Diophantine equations in six variables. We prove that every symmetric form of odd degree n ≥ 5 in 6 . 2n-5 variables has a rational parametric solution depending on 2n -- 8 parameters. We also present a solution to a problem of Waring type: if F(xi,..., xN) is a symmetric form of odd degree n ≥ 5 in N = 6 . 2n-4 variables, then for any q ∈ Q the equation F(x¡) = q has a rational parametric solution depending on 2n -- 6 parameters. [ABSTRACT FROM AUTHOR]

Abstract: We give a short proof of the two disjoint odd cycles theorem which characterizes graphs without two vertex-disjoint odd cycles. Our proof does not depend on any matroid result. It only uses the two paths theorem, which characterizes graphs without two disjoint paths with specified ends (i.e., 2-linked graphs). [Copyright &y& Elsevier]

Let G be a finite group and letΓ (G) be the prime graph of G. We assume that n is an odd number. In this paper, we show that if Γ(G) = Γ(Cn(2)), where n ≠ 3, then G has a unique nonabelian composition factor isomorphic to Cn(2). As consequences of our result, Cn(2) is quasirecognizable by its spectrum and by a new proof the validity of a conjecture of W. J. Shi for Cn(2) is obtained. [ABSTRACT FROM AUTHOR]